Going further · 21
Recursion
A function that calls itself: base cases, call-stack depth, loops and memoization.
Recursion is a function calling itself.
The example below sums the digits of a number recursively (digit_sum(12345) is 5 + digit_sum(1234)) and computes a Fibonacci number while remembering the values it has found.
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){ if (n < 10) { return n; } return n % 10 + digitSum(Mathf.Quot(n, 10));} fib(k, memo){ if (k <= 1) { return k; } if (memo[k] == 0) { memo[k] = fib(k - 1, memo) + fib(k - 2, memo); } return memo[k];} n = Console.ReadLine().ToNumber();k = Console.ReadLine().ToNumber();Console.WriteLine(digitSum(n));Console.WriteLine(fib(k, NewList(k + 1, 0)));12345 50
15 12586269025
Key points
- Shrink a big problem into a smaller one of the same shape.
Once it is too small to shrink, return the answer directly: that is the base case. - The syntax is the same as any function.
The only difference is that the function calls its own name inside. - Every call pushes its parameters and locals onto the call stack, and every return pops them off.
So depth is limited. - For work that runs in a straight line (summing 1 to n, counting down), a loop is better: no depth limit, and faster.
Recursion shines when work branches: folders inside folders, tree-shaped data, trying every possibility. - Remember each value in a map or array once it's computed (memoization), and nothing is computed twice.
Grow this idea into a table and you get dynamic programming.
How each language writes it
| Python | def f(n): calling f(n - 1) — the default depth limit is 1000, beyond which it raises RecursionError.Putting @functools.cache above the function memoizes it |
|---|---|
| JavaScript | function f(n) { } — too deep throws RangeError: Maximum call stack size exceeded |
| TypeScript | Same as JavaScript |
| Java | Return type in front (static int f(int n)) — too deep throws StackOverflowError |
| C# | static int F(int n) — StackOverflowException cannot be caught with catch, so the program simply terminates |
| C++ | int f(int n) — running out of stack usually crashes with Segmentation fault |
| C | Same as C++ |
| Craykon | name(params) { } with return — stops after a few thousand levels with "functions were called too deeply".Lists aren't copied when passed, so every call shares the example's memo list ( NewList(k + 1, 0)) |
Common mistakes
It never reaches the base case
def f(n):
if n == 0:
return 0
return n + f(n)→ f(n) calls itself forever until a depth error stops it
Shrink toward the base every time (f(n - 1)).
Before writing, check when it stops and whether each call gets closer.
Fibonacci without a memo
def fib(k):
if k <= 1:
return k
return fib(k - 1) + fib(k - 2)→ It recomputes the same values over and over: fib(50) makes tens of billions of calls
Store each value in a map or array, and it finishes in about 100 calls.
How languages differ
Recursion must have a base case, and every call must move toward it.
If the depth could reach the thousands (say, input n up to 100,000), write it as a loop from the start.
Recursion must have a base case, and every call must move toward it.
If the depth could reach the thousands (say, input n up to 100,000), write it as a loop from the start.