階乗（再帰）
階乗（再帰）
このレッスンで分かること
- 必ず
基底ケースがある (= 終わる条件がある) 2. 再帰呼び出しは基底ケースに近づく方向にだけ進む- 再帰版と比べると、
変数 resultを導入して1から順に掛けていく形になります再帰は「関数が自分自身を呼ぶ」プログラミング手法です
階乗 とは
再帰関数の基本パターンを
factorial(n)で体感する。停止条件と自己呼び出しの考え方を身につける。
再帰 は「関数が自分自身を呼ぶ」プログラミング手法です。ループ for や while と並ぶ、繰り返しの第三の道具と考えてよいでしょう。本章では最も有名な再帰の題材である 階乗 を題材に、再帰の 基底ケース と 再帰ケース の考え方を身につけます。
再帰は「ループの別表現」ではなく、「問題を一段小さい同じ問題に置き換える」発想だ。
階乗は数学では n! と書き、5! = 5 * 4 * 3 * 2 * 1 = 120 と定義されます。0 の階乗は 0! = 1、1 の階乗も 1! = 1 です。これが再帰における 基底ケース (停止条件) になります。
再帰関数のテンプレート
どの言語の再帰でも、骨格は同じです。基底ケース を最初に書き、それ以外は自分自身を呼ぶ、というだけ。次の Mermaid 図で「factorial(4) がどう展開されるか」を見てみましょう。
図のポイント (テキスト併記)
- 上から下に「呼び出しが深くなる」、
factorial(1)まで降りたら反対方向に値が戻るイメージです
上から下に「呼び出しが深くなる」、factorial(1) まで降りたら反対方向に 値が戻る イメージです。これは コールスタック という仕組みで、関数呼び出しは スタック に積まれます。基底ケースに到達したら、積まれた呼び出しを pop しながら計算を巻き戻していくわけです。
Python での実装
Python
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)if n <= 1: return 1 が 基底ケース です。n が 2 以上のときは、n * factorial(n - 1) で自分自身を呼びます。n を 1 ずつ減らすことで、いつか必ず 基底ケース に到達します。
JavaScript での実装
JavaScript
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}同じロジックを JavaScript で書くと、ほぼ同じ姿になります。再帰 は言語をまたいで普遍的な書き方、ということがよく分かります。
Java での実装
Java
public class Solution {
public static long factorial(int n) {
if (n <= 1) return 1L;
return n * factorial(n - 1);
}
}Java では long を使う点に注意してください。int だと 13! 付近で オーバーフロー します。
再帰の 2 つの条件
- 必ず
基底ケースがある (= 終わる条件がある)- 再帰呼び出しは
基底ケースに近づく方向にだけ進む
この 2 つを守らないと、StackOverflowError (スタックオーバーフロー) が起きてプログラムが落ちます。再帰 は強力ですが、無限ループ と同じく無限再帰を作ってしまう罠もあるので注意です。
よくある間違い
基底ケースの境界をn == 0だけにすると、負の値を渡されたときに無限再帰になる。n <= 1のように<=で書くのが安全。return n * factorial(n - 1)のreturnを忘れて、ただ呼ぶだけ書いてしまうと、計算結果が捨てられる。- ループの方が速い場合がほとんど。
再帰は「書きやすさ」のための道具と考える。
やってみよう
下の coding 課題で、factorial(n) を 再帰 で実装してください。基底ケース と 再帰呼び出し の 2 行が書ければ完成です。テストでは 0 から 10 までの値で正しい階乗が返るかを確認します。for ループは使わず、必ず 再帰 で書いてください。
再帰のリズムを体に染み込ませるには、
紙とペンでfactorial(4)の呼び出しを 1 段ずつ書き下すのが効く。コールスタックの上下を意識すると、デバッグ力が一気に上がる。
補足: ループ版との比較
参考までに、for ループで書いた factorial も並べておきます。
Python
def factorial_loop(n):
result = 1
for i in range(2, n + 1):
result *= i
return result再帰版と比べると、変数 result を導入して 1 から順に掛けていく形になります。再帰 は「数式に近い書き方」、ループ は「機械的な書き方」と言えるかもしれません。関数型プログラミング の世界では再帰がよく使われるのに対し、手続き型プログラミング ではループが好まれる傾向があります。どちらも O(n) で動作するため、計算量的には同じです。
本レッスンで覚えてほしいのは、数式に近い形 で書ける 再帰 の表現力です。第 6 章 (動的計画法) で再び再帰を扱うときの土台になります。
よくある質問
Q. 再帰とループはどっちを使うべき？
A. ツリー構造や分割統治（merge sort, BST 走査）は再帰が自然で読みやすくなります。シンプルな反復処理はループが速くスタックも消費しません。再帰深さが配列長に比例する場合、スタックオーバーフローのリスクがあるため気をつけてください。
Q. 再帰のベースケースを忘れるとどうなる？
A. 無限再帰になりスタックオーバーフローします。最初の 1 行目に if (base) return; を書く習慣を付けると安全です。Python は sys.setrecursionlimit で上限を変えられますが、根本的にループに書き換える方が安定します。
Q. 再帰を高速化する方法は？
A. 同じ引数で再計算しているなら memoize（メモ化）で結果をキャッシュします。Python は functools.lru_cache、Java/JS は HashMap で実装します。フィボナッチを memo 付きにすると指数 O(2ⁿ) から線形 O(n) に劇的に高速化します。
次のレッスン
次は フィボナッチ数（再帰） で、fib(n-1) + fib(n-2) のように再帰呼び出しを 2 つ持つパターンを学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 階乗 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 階乗 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 関数
factorial(n)を実装し、整数値を返す - for / while を使わず、必ず再帰呼び出しで実装する
- 基底ケース (n <= 1) を最初に書き、それ以外は n * factorial(n - 1) を返す
入出力例
test-cases.txt
factorial(0) → 1
factorial(1) → 1
factorial(5) → 120
factorial(6) → 720
factorial(10) → 3628800