学ぶ › JavaScript
さらに先へ · 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 段積まれ、返ると 1 段降ります。
そのため深さには限界があります。 - 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 万など）なら、最初からループで書きましょう。