더 나아가기 · 21
재귀
함수가 자기 자신을 불러요. 바닥 조건, 호출 스택의 깊이, 반복문과 메모까지.
재귀는 함수가 자기 자신을 부르는 거예요.
아래 예제는 자릿수의 합을 재귀로 구하고(digit_sum(12345)는 5 + digit_sum(1234)), 피보나치 수를 메모해 가며 구해요.
def digit_sum(n): if n < 10: # 바닥: 한 자리면 그대로 return n return n % 10 + digit_sum(n // 10) memo = {} def fib(k): if k <= 1: # 바닥 return k if k not in memo: # 한 번 구한 값은 적어 두기 memo[k] = fib(k - 1) + fib(k - 2) return memo[k] n = int(input())k = int(input())print(digit_sum(n))print(fib(k))function digitSum(n) { if (n < 10) return n; // 바닥: 한 자리면 그대로 return (n % 10) + digitSum(Math.trunc(n / 10));} const memo = new Map();function fib(k) { if (k <= 1) return k; // 바닥 if (!memo.has(k)) memo.set(k, fib(k - 1) + fib(k - 2)); // 한 번 구한 값은 적어 두기 return memo.get(k);} const [n, k] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);console.log(digitSum(n));console.log(fib(k));import { readFileSync } from "node:fs"; function digitSum(n: number): number { if (n < 10) return n; // 바닥: 한 자리면 그대로 return (n % 10) + digitSum(Math.trunc(n / 10));} const memo = new Map<number, number>();function fib(k: number): number { if (k <= 1) return k; // 바닥 if (!memo.has(k)) memo.set(k, fib(k - 1) + fib(k - 2)); // 한 번 구한 값은 적어 두기 return memo.get(k)!;} const [n, k]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);console.log(digitSum(n));console.log(fib(k));import java.util.Scanner; public class Main { static int digitSum(int n) { if (n < 10) return n; // 바닥: 한 자리면 그대로 return n % 10 + digitSum(n / 10); } static long[] memo = new long[91]; static long fib(int k) { if (k <= 1) return k; // 바닥 if (memo[k] == 0) memo[k] = fib(k - 1) + fib(k - 2); // 한 번 구한 값은 적어 두기 return memo[k]; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(), k = in.nextInt(); System.out.println(digitSum(n)); System.out.println(fib(k)); }}using System;using System.Collections.Generic; class Program{ static int DigitSum(int n) { if (n < 10) return n; // 바닥: 한 자리면 그대로 return n % 10 + DigitSum(n / 10); } static readonly Dictionary<int, long> Memo = new(); static long Fib(int k) { if (k <= 1) return k; // 바닥 if (!Memo.ContainsKey(k)) Memo[k] = Fib(k - 1) + Fib(k - 2); // 한 번 구한 값은 적어 두기 return Memo[k]; } static void Main() { int n = int.Parse(Console.ReadLine()); int k = int.Parse(Console.ReadLine()); Console.WriteLine(DigitSum(n)); Console.WriteLine(Fib(k)); }}#include <iostream>#include <unordered_map> int digitSum(int n) { if (n < 10) return n; // 바닥: 한 자리면 그대로 return n % 10 + digitSum(n / 10);} std::unordered_map<int, long long> memo; long long fib(int k) { if (k <= 1) return k; // 바닥 if (!memo.count(k)) memo[k] = fib(k - 1) + fib(k - 2); // 한 번 구한 값은 적어 두기 return memo[k];} int main() { int n, k; std::cin >> n >> k; std::cout << digitSum(n) << '\n'; std::cout << fib(k) << '\n';}#include <stdio.h> int digit_sum(int n) { if (n < 10) return n; /* 바닥: 한 자리면 그대로 */ return n % 10 + digit_sum(n / 10);} long long memo[91]; /* 전역 배열은 0으로 시작해요 */ long long fib(int k) { if (k <= 1) return k; /* 바닥 */ if (memo[k] == 0) memo[k] = fib(k - 1) + fib(k - 2); /* 한 번 구한 값은 적어 두기 */ return memo[k];} int main(void) { int n, k; scanf("%d %d", &n, &k); printf("%d\n", digit_sum(n)); printf("%lld\n", fib(k)); return 0;}digitSum(n){ 만약 (n < 10) { 돌려주기 n; } 돌려주기 n % 10 + digitSum(수학.몫(n, 10));} fib(k, memo){ 만약 (k <= 1) { 돌려주기 k; } 만약 (memo[k] == 0) { memo[k] = fib(k - 1, memo) + fib(k - 2, memo); } 돌려주기 memo[k];} n = 콘솔.줄읽기().수로변환();k = 콘솔.줄읽기().수로변환();콘솔.쓰기(digitSum(n));콘솔.쓰기(fib(k, 새목록(k + 1, 0)));12345 50
15 12586269025
핵심
- 큰 문제를 같은 모양의 더 작은 문제로 줄여요.
더 줄일 수 없을 만큼 작아지면 바로 답을 돌려주는데, 이것이 바닥 조건(base case)이에요. - 쓰는 법은 함수와 같아요.
다른 점은 함수 안에서 자기 이름을 다시 부른다는 것뿐이에요. - 부를 때마다 매개변수와 지역 변수가 호출 스택에 한 칸씩 쌓이고, 돌려주면 한 칸 빠져요.
그래서 깊이에 한계가 있어요. - 한 줄로 쭉 가는 일(1부터 n까지 더하기, 거꾸로 세기)은 반복문이 더 나아요.
깊이 제한이 없고 더 빨라요.
재귀는 갈래가 나뉘는 일(폴더 안의 폴더, 나무 모양 자료, 모든 경우 해 보기)에서 빛나요. - 한 번 구한 값을 사전이나 배열에 적어 두면(메모이제이션) 같은 계산을 되풀이하지 않아요.
이 생각을 표로 넓힌 것이 동적 계획법이에요.
언어별로 쓰는 법
| Python | def f(n): 안에서 f(n - 1) — 기본 깊이 한도가 1000단계라 넘으면 RecursionError.함수 위에 @functools.cache만 붙여도 메모가 돼요 |
|---|---|
| JavaScript | function f(n) { } — 너무 깊으면 RangeError: Maximum call stack size exceeded |
| TypeScript | JavaScript와 같아요 |
| Java | 돌려주는 타입을 앞에 적어요(static int f(int n)) — 너무 깊으면 StackOverflowError |
| C# | static int F(int n) — StackOverflowException은 catch로 잡을 수 없어서 프로그램이 그대로 끝나요 |
| C++ | int f(int n) — 스택을 넘으면 보통 Segmentation fault로 죽어요 |
| C | C++와 같아요 |
| Craykon | 이름(매개변수) { } 안에서 돌려주기 — 몇천 단계에서 "함수를 너무 깊이 불러서 멈췄어요"라고 알려 줘요.목록은 넘겨도 복사되지 않아서, 예제의 메모 목록( 새목록(k + 1, 0))을 모든 호출이 함께 써요 |
자주 하는 실수
바닥에 닿지 않아요
def f(n):
if n == 0:
return 0
return n + f(n)→ f(n)이 끝없이 자기를 불러서 결국 깊이 오류로 멈춰요
매번 바닥 쪽으로 줄여요(f(n - 1)).
쓰기 전에 '언제 멈추나'와 '매번 바닥에 가까워지나'를 확인해요.
메모 없이 피보나치를 구했어요
def fib(k):
if k <= 1:
return k
return fib(k - 1) + fib(k - 2)→ 같은 값을 몇 번이고 다시 구해서 fib(50)은 수백억 번을 불러요
구한 값을 사전이나 배열에 적어 두면 100번쯤만 부르면 끝나요.
언어마다 다른 점
재귀에는 반드시 바닥 조건이 있어야 하고, 매번 그쪽으로 다가가야 해요.
깊이가 몇천을 넘을 수 있는 문제(입력 n이 10만 등)라면 처음부터 반복문으로 쓰세요.
재귀에는 반드시 바닥 조건이 있어야 하고, 매번 그쪽으로 다가가야 해요.
깊이가 몇천을 넘을 수 있는 문제(입력 n이 10만 등)라면 처음부터 반복문으로 쓰세요.