进阶 · 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 万），一开始就写成循环。