目次
再帰的アルゴリズムとは
再帰的アルゴリズムとは、関数が自分自身を呼び出すことで処理を進めるプログラミング技法です。通常の繰り返し構造（for文やwhile文）と異なり、再帰は「問題をより小さな同型の問題に分割し、最終的に基底条件（出口）に到達することで終了する」という考え方に基づいています。これにより、複雑な処理をシンプルで直感的な形に表現できるのが大きな特徴です。
オルビナ/基本情報技術者専門官その壱の再帰的アルゴリズムでは、再帰的アルゴリズムの基本について解説しています。理解をさらに深めたい方は、ぜひ下の関連記事も読んでみてくださいね。
ITTI DX
再帰的アルゴリズムとは？ループ防止の仕組みについて【ITTI】
複雑な処理をシンプルに表現できる再帰的アルゴリズム。基底条件・再帰呼び出し・問題分割を具体例で解説し、無限ループを防ぐ仕組みを理解できます。
基本パターン
階乗計算（factorial）
function factorial(n):
if n = 0 then return 1 ← 基底条件（出口）
else return n × factorial(n-1) ← 再帰呼び出し
ここまでは階乗計算のコードを用意しました。これで階乗計算を実行できます。factorial(4) を呼び出すと次のように処理が進みます。
• factorial(4) → 4 × factorial(3)
• factorial(3) → 3 × factorial(2)
• factorial(2) → 2 × factorial(1)
• factorial(1) → 1 × factorial(0)
• factorial(0) → 1 （基底条件で終了、つまり出口です）
実行結果
4! = 4×3×2×1 = 24階乗計算とは、1からその数 n までの連続した整数をすべて掛け合わせた積を求める計算のことです。記号「!」を使って n! と表します。例えば、n=4 を設定して呼び出すと、
4! = 4 × 3 × 2 × 1 = 24
となります。これが階乗計算です。
フィボナッチ数列
function fibonacci(n):
if n ≤ 1 then return n ← 基底条件（出口）
else return fibonacci(n-1) + fibonacci(n-2) ← 再帰呼び出し
ここまでは階乗計算のコードを用意しました。これで階乗計算を実行できます。fibonacci(4) を呼び出します。
最初は大きいところから始めます。
◦ fibonacci(4) = fibonacci(3) + fibonacci(2)
◦ fibonacci(3) = fibonacci(2) + fibonacci(1)
◦ fibonacci(2) = fibonacci(1) + fibonacci(0)
◦ fibonacci(1) = 1, fibonacci(0) = 0 （出口）ここから再帰呼び出しに入ります
最初は小さいところから始めます。
• F(2) = 1 + 0 = 1
• F(3) = F(2) + F(1) = 1 + 1 = 2
• F(4) = F(3) + F(2) = 2 + 1 = 3（出口）
F(4) = F(3) + F(2) = 2 + 1 = 3は最後の結果なので3です。
計算結果：
fibonacci(4) = 3配列の合計
function arraySum(A, i):
if i ≥ length(A) then return 0 ← 基底条件（出口）
else return A[i] + arraySum(A, i+1) ← 再帰呼び出し
ここまでは配列の合計のコードを用意しました。これで配列の合計を実行できます。配列 A = [2, 4, 6] の合計を求めたいとき、arraySum(A, 0) を呼び出します。
arraySum(A,0)
= A[0] + arraySum(A,1)
A[0]は[2, 4, 6]の内、2を選択してます、よって2です。足すのはまだです。
= 2 + arraySum(A,1)
arraySum(A,1)
= A[1] + arraySum(A,2)
A[1]は[2, 4, 6]の内、4を選択してます、よって4です。足すのはまだです。
= 4 + arraySum(A,2)
arraySum(A,2)
= A[2] + arraySum(A,3)
A[2]は[2, 4, 6]の内、6を選択してます、よって6です。足すのはまだです。
= 6 + arraySum(A,3)
arraySum(A,3)
配列外なので0です。ここから出口に出ます。
= 0 （i=3 ≥ length(A)=3 なので出口）ここから再帰呼び出しに入ります。
足すのはここからです、計算してみましょう。
数が大きい順からスタートです。
arraySum(A,2) = 6 + 0 = 6
arraySum(A,1) = 4 + 6 = 10
arraySum(A,0) = 2 + 10 = 12（出口）
実行結果は12です。
まとめ
arraySum([2,4,6],0) = 2 + (4 + (6 + 0)) = 12再帰呼び出しは計算のスタート、基底条件は計算の終了です。この考え方は試験に出やすいので、しっかり理解しておきましょう。
コメント