再帰法とは？再帰関数・終了条件・スタックとの関係を基礎から理解しよう

はじめに

これまでの記事では、

スタック
木構造
DFS
クイックソート
マージソート

などを学んできました。

これらを学ぶ中で何度か登場したのが、

再帰（Recursion）

です。

再帰を簡単にいうと、

ある処理の中から、同じ処理をもう一度呼び出す考え方

です。

例えば、

処理A
↓
処理A
↓
処理A
↓
...

のように、同じ処理を繰り返し呼び出します。

ただし、永遠に呼び出し続けてはいけません。

そこで重要になるのが、

再帰呼出し
+
終了条件

です。

この記事では、

再帰とは
↓
再帰関数
↓
終了条件
↓
階乗
↓
スタックとの関係
↓
フィボナッチ数列
↓
木構造・DFS
↓
反復処理との違い

という順番で学んでいきます。

---

1. 再帰とは

**再帰（Recursion）**とは、

あるものを、そのもの自身を使って定義・処理する考え方

です。

プログラムでは特に、

関数が自分自身を呼び出す

形で利用されます。

例えば、

function A()
    ↓
    function A()
        ↓
        function A()

というような構造です。

このような関数を**再帰関数（Recursive Function）**と呼びます。

---

2. 再帰関数とは

通常の関数では、

main
↓
function A

のように、別の関数を呼び出します。

再帰関数では、

function A
↓
function A
↓
function A

のように、自分自身を呼び出します。

例えば疑似コードなら、

function countdown(n)

    print(n)

    countdown(n - 1)

のような処理です。

countdown(3)を実行すると、

countdown(3)
↓
countdown(2)
↓
countdown(1)
↓
countdown(0)
↓
countdown(-1)
↓
...

となります。

このままでは問題があります。

---

3. このままだと永遠に終わらない

先ほどの処理には、

いつ再帰を終了するのか

という条件がありません。

そのため、

3
↓
2
↓
1
↓
0
↓
-1
↓
-2
↓
...

と呼び出し続けてしまいます。

そこで再帰処理では、必ず終了条件を用意する必要があります。

---

4. 終了条件とは

例えば、

function countdown(n)

    if n == 0
        return

    print(n)

    countdown(n - 1)

とします。

この場合、

n == 0

になったら、それ以上自分自身を呼び出しません。

countdown(3)なら、

countdown(3)
↓
countdown(2)
↓
countdown(1)
↓
countdown(0)
↓
終了

となります。

このように、再帰処理を止めるための条件を**基底条件（Base Case）**などと呼びます。

---

5. 再帰法の基本構造

再帰関数には、大きく2つの要素があります。

① 終了する条件

② 自分自身を呼び出す処理

疑似コードなら、

function recursive(n)

    if 終了条件
        return

    recursive(次の値)

という形です。

つまり、

「いつ終わるのか」と「終了条件へどう近づくのか」

の両方が重要です。

終了条件が存在していても、そこへ近づかなければ再帰は終了しません。

---

6. 階乗を再帰で考えてみる

再帰法の代表例が**階乗（Factorial）**です。

例えば、

5!

は、

5 × 4 × 3 × 2 × 1
=
120

です。

ここで、

5!
=
5 × 4!

と考えることができます。

さらに、

4!
=
4 × 3!

です。

つまり、

5!
=
5 × 4!

4!
=
4 × 3!

3!
=
3 × 2!

2!
=
2 × 1!

となります。

同じ形が何度も登場しています。

これが再帰と相性のよい構造です。

---

7. 階乗を再帰関数にする

階乗は、

n!
=
n × (n - 1)!

と表せます。

ただし、このままでは永遠に続いてしまいます。

そこで、

0! = 1

を終了条件として利用できます。

疑似コードなら、

function factorial(n)

    if n == 0
        return 1

    return n * factorial(n - 1)

となります。

---

8. factorial(3)を追いかけてみる

例えば、

factorial(3)

を実行します。

まず、

factorial(3)
=
3 × factorial(2)

です。

さらに、

factorial(2)
=
2 × factorial(1)

さらに、

factorial(1)
=
1 × factorial(0)

そして、

factorial(0)
=
1

となります。

ここで再帰呼出しが終了します。

---

9. 今度は逆向きに戻っていく

終了条件まで到達すると、今度は計算結果が戻っていきます。

factorial(0)
=
1

なので、

factorial(1)
=
1 × 1
=
1

さらに、

factorial(2)
=
2 × 1
=
2

さらに、

factorial(3)
=
3 × 2
=
6

となります。

つまり、

呼び出す

3
↓
2
↓
1
↓
0

戻る

0
↓
1
↓
2
↓
3

という動きをしています。

---

10. 再帰とスタック

ここで、以前学んだスタックが登場します。

関数を呼び出すと、

どの関数を実行していたか
どこへ戻るか
引数などの情報

を管理する必要があります。

こうした関数呼出しの情報は、一般に**コールスタック（Call Stack）**と呼ばれるスタック構造で管理されます。

スタックは、

LIFO
=
後入れ先出し

でした。

再帰処理と非常に相性のよい構造です。

---

11. factorial(3)とスタック

factorial(3)を実行すると、概念的には、

factorial(3)

がスタックへ積まれます。

さらに、

factorial(2)
factorial(3)

さらに、

factorial(1)
factorial(2)
factorial(3)

さらに、

factorial(0)
factorial(1)
factorial(2)
factorial(3)

というように呼出しが積み重なります。

---

12. 終了するとPOPされていく

factorial(0)が終了すると、

factorial(0)

の処理が終了し、呼出し元へ戻ります。

その後、

factorial(1)
↓
factorial(2)
↓
factorial(3)

という順番で処理が戻っていきます。

これはまさに、

最後に呼び出したもの
↓
最初に戻る

というLIFOの動作です。

🍯 再帰とスタックはセット

で理解しておきましょう。

---

13. スタックフレームとは

関数が呼び出されると、その関数を実行するための情報を保存する領域が必要になります。

このような関数呼出しごとの情報をまとめたものを**スタックフレーム（Stack Frame）**と呼びます。

概念的には、

┌─────────────────┐
│ factorial(0)    │
├─────────────────┤
│ factorial(1)    │
├─────────────────┤
│ factorial(2)    │
├─────────────────┤
│ factorial(3)    │
└─────────────────┘

のように積み重なります。

スタックフレームには実装や処理系に応じて、

引数
ローカル変数
戻り先などの情報

が管理されます。

---

14. 再帰が深すぎるとどうなる？

再帰処理では、呼出しのたびにスタックを使用します。

例えば、

function(100000)
↓
function(99999)
↓
function(99998)
↓
...

のように大量の再帰呼出しを行うと、スタック領域を大量に使用します。

利用できるスタック領域を超えると、

スタックオーバーフロー（Stack Overflow）

が発生する可能性があります。

つまり、

再帰
↓
関数呼出しが積まれる
↓
スタックを使用
↓
深すぎる
↓
スタックオーバーフロー

という関係です。

---

15. 無限再帰

終了条件が間違っている場合も危険です。

例えば、

function count(n)

    print(n)

    count(n + 1)

のような処理では、自分自身を呼び続けます。

1
↓
2
↓
3
↓
4
↓
...

このように再帰呼出しが終了しない状態を無限再帰と呼びます。

最終的には、スタック領域を使い切るなどしてエラーになる可能性があります。

---

16. 終了条件があるだけではダメ

例えば、

if n == 0
    return

という終了条件があっても、

recursive(n + 1)

と処理していたら、

3
↓
4
↓
5
↓
6

となり、0へ近づきません。

つまり再帰では、

終了条件がある
+
再帰するたび終了条件へ近づく

ことが重要です。

---

17. フィボナッチ数列と再帰

再帰の代表例としてフィボナッチ数列もあります。

例えば、

0, 1, 1, 2, 3, 5, 8, 13, ...

という数列です。

基本的には、

F(n)
=
F(n - 1) + F(n - 2)

という関係があります。

例えば、

F(5)
=
F(4) + F(3)

です。

---

18. フィボナッチ数列を再帰で書く

疑似コードなら、

function fibonacci(n)

    if n == 0
        return 0

    if n == 1
        return 1

    return fibonacci(n - 1)
         + fibonacci(n - 2)

となります。

数式の定義を、そのままプログラムへ落とし込んだような形です。

これは再帰の分かりやすい特徴です。

---

19. でも再帰なら何でも効率的？

ここは重要です。

再帰を使えば必ず効率がよくなるわけではありません。

先ほどの単純なフィボナッチ数列の再帰では、

F(5)
├─ F(4)
│  ├─ F(3)
│  └─ F(2)
│
└─ F(3)
   ├─ F(2)
   └─ F(1)

のように、同じ計算が何度も登場します。

例えば、

F(3)

を複数回計算しています。

そのため、単純な再帰実装では非常に多くの計算が必要になる場合があります。

---

20. 再帰は「分かりやすさ」と「効率」が同じとは限らない

フィボナッチ数列の例では、

F(n)
=
F(n - 1) + F(n - 2)

という定義をそのまま書けるため、再帰を使うとコードは理解しやすくなります。

一方で、

同じ計算を繰り返す

という問題があります。

つまり、

再帰で書きやすい = 最も効率がよい

とは限りません。

アルゴリズムでは、

分かりやすさ
処理時間
メモリ使用量

などを考える必要があります。

---

21. メモ化という考え方

同じ計算を何度も行う問題を改善する方法の一つが**メモ化（Memoization）**です。

一度計算した、

F(3) = 2

などの結果を保存しておきます。

次にF(3)が必要になったら、

もう一度計算

するのではなく、

保存済みの結果を利用

します。

これによって重複した計算を減らせます。

この考え方は、後に学ぶ動的計画法にもつながります。

---

22. 木構造と再帰

再帰は木構造と非常に相性がよいです。

例えば、

        A
       / \
      B   C
     / \
    D   E

という木があります。

Aから見ると、

A
├─ 左部分木
└─ 右部分木

があります。

そして左部分木のBから見ても、

B
├─ 左部分木
└─ 右部分木

という同じような構造になっています。

つまり、

木の中に、同じ構造を持つ小さな木がある

と考えられます。

---

23. 木を再帰で処理する

例えば前順走査なら、

preorder(node)

    nodeを処理

    左部分木をpreorder

    右部分木をpreorder

と表現できます。

つまり、

木を処理する
↓
左の木を同じ方法で処理
↓
右の木を同じ方法で処理

という再帰処理です。

木構造自体が再帰的な構造を持っているため、再帰関数で自然に表現できます。

---

24. DFSと再帰

前回学んだ**深さ優先探索（DFS）**でも再帰を利用できます。

例えば、

DFS(node)

    nodeを訪問済みにする

    接続されているノードについて
        まだ訪問していなければ
            DFS(そのノード)

という形です。

A
↓
B
↓
D

と深い方向へ進み、行き止まりになったら戻ります。

この、

進む
↓
進む
↓
進む
↓
戻る

という動作を、再帰とコールスタックによって表現できます。

---

25. クイックソートと再帰

前回学んだクイックソートでも再帰が利用されます。

クイックソートでは、

データ
↓
ピボットで分割
↓
左側
右側

と分けます。

そして、

左側をクイックソート
右側をクイックソート

します。

つまり、

quickSort(data)

    データを分割

    quickSort(左側)

    quickSort(右側)

という再帰的な処理として表現できます。

---

26. マージソートと再帰

マージソートも同様です。

データ
↓
半分に分割
↓
左半分
右半分

そして、

左半分をマージソート
右半分をマージソート

します。

最後に、

整列しながら結合

します。

つまり、

大きな問題
↓
小さな同じ問題
↓
さらに小さな同じ問題

という構造になっています。

---

27. 分割統治法と再帰

クイックソートやマージソートでは、**分割統治法（Divide and Conquer）**という考え方を使いました。

分割統治法は、

大きな問題
↓
小さな問題へ分割
↓
それぞれを解く
↓
結果を組み合わせる

という方法です。

分割した後にも、

元と同じ種類の問題

が現れることが多いため、再帰と非常に相性があります。

例えばマージソートなら、

8個を整列
↓
4個を整列
↓
2個を整列
↓
1個

となり、1個になれば終了できます。

---

28. 再帰法と反復法

同じ処理を繰り返す方法には、再帰だけでなく**反復（Iteration）**もあります。

例えば、

1
2
3
4
5

を処理するなら、

for
while

などのループを利用できます。

このようにループを使って繰り返す方法を、再帰法と対比して反復法と呼ぶことがあります。

---

29. 階乗を反復で書く

階乗は再帰だけでなく、ループでも計算できます。

例えば、

result = 1

for i = 1 から n
    result = result * i

とすれば、

1
↓
1 × 2
↓
2 × 3
↓
6 × 4
↓
...

と計算できます。

つまり、

再帰法
→ 自分自身を呼び出す

反復法
→ ループを繰り返す

という違いがあります。

---

30. 再帰法と反復法の違い

整理すると、

項目	再帰法	反復法
基本	自分自身を呼び出す	ループを使う
主な終了方法	基底条件	ループ条件
スタック	呼出しごとに使用	通常は再帰ほど使用しない
得意な処理	木・分割統治など	単純な繰返しなど
注意点	深すぎる再帰	無限ループなど

どちらが常に優れているというわけではありません。

処理に応じて使い分けます。

---

31. 再帰を使うメリット

再帰の大きなメリットは、

再帰的な構造を持つ問題を自然に表現できる

ことです。

例えば、

木構造
DFS
階乗
分割統治法

などです。

特に木構造では、

木を処理
↓
左の木を処理
↓
右の木を処理

という構造を、そのままプログラムとして表現できます。

複雑な処理でもコードを簡潔に書ける場合があります。

---

32. 再帰を使うデメリット

一方で、再帰には注意点もあります。

スタックを使用する

呼出しごとにスタックフレームが積まれるため、深い再帰ではメモリを多く使用します。

スタックオーバーフローの可能性

再帰が深すぎるとスタック領域を使い切る可能性があります。

処理を追いにくい場合がある

呼出し
↓
さらに呼出し
↓
さらに呼出し
↓
戻る
↓
戻る

という処理になるため、慣れないうちは実行順序が分かりにくいことがあります。

同じ計算を繰り返す場合がある

単純なフィボナッチ数列の再帰のように、同じ処理を何度も行う場合があります。

---

33. 末尾再帰とは

再帰には**末尾再帰（Tail Recursion）**という形もあります。

末尾再帰とは、

関数の最後の処理が再帰呼出しになっている再帰

です。

例えば概念的には、

function count(n)

    if n == 0
        return

    print(n)

    return count(n - 1)

のような形です。

再帰呼出しの後に追加の処理を行わないことが特徴です。

---

34. 末尾再帰の最適化

言語や処理系によっては、末尾再帰をループに近い形へ変換し、スタックの使用量を抑える末尾呼出し最適化が行われる場合があります。

ただし、

末尾再帰なら必ず最適化される

わけではありません。

プログラミング言語や処理系によって対応が異なります。

そのため、末尾再帰そのものと、末尾呼出し最適化は分けて理解しておきましょう。

---

35. 再帰処理を読むコツ

再帰処理が出てきたら、いきなり頭の中だけで処理しようとすると混乱しやすくなります。

まず、

① 終了条件を探す

次に、

② 次の再帰呼出しで何が変化するか確認

そして、

③ 実際の値を入れて呼出しを展開

します。

例えば、

factorial(3)

なら、

factorial(3)
↓
factorial(2)
↓
factorial(1)
↓
factorial(0)

と紙に書いてしまいます。

その後、

factorial(0)
↓
factorial(1)
↓
factorial(2)
↓
factorial(3)

と戻る処理を追います。

---

36. 応用情報で再帰問題を考えるポイント

再帰関数が出てきた場合は、次の3点に注目します。

① 終了条件は何か

② 再帰呼出し時に引数がどう変化するか

③ 戻るときに何を計算するか

例えば、

function f(n)

    if n == 0
        return 1

    return n * f(n - 1)

なら、

終了条件

n == 0

引数

n
↓
n - 1

戻るとき

n × 戻り値

です。

この3つに分解すると、再帰処理を追いやすくなります。

---

37. これまで学んだ内容とのつながり

ここまでのアルゴリズムの記事を整理すると、

スタック
↓
関数呼出しを管理
↓
再帰

というつながりがあります。

さらに、

再帰
├─ 木の走査
├─ DFS
├─ クイックソート
└─ マージソート

へつながります。

そして、

再帰
↓
同じ計算が重複する場合がある
↓
メモ化
↓
動的計画法

という次のアルゴリズムにもつながっていきます。

再帰は単独の知識ではなく、さまざまなアルゴリズムを理解するための基礎となる考え方です。

---

38. まとめ

再帰法とは、

処理の中から同じ処理を呼び出すことで問題を解く方法

です。

プログラムでは、自分自身を呼び出す再帰関数として表現されます。

ただし、再帰には必ず、

終了条件

が必要です。

さらに、

再帰するたび
↓
終了条件へ近づく

必要があります。

再帰呼出しでは関数の情報がスタックへ積まれ、

呼出し
↓
呼出し
↓
終了条件
↓
戻る
↓
戻る

という処理になります。

この記事で覚えること

• 再帰とは自分自身を使って処理を定義する考え方
• 自分自身を呼び出す関数を再帰関数という
• 再帰処理には終了条件が必要
• 終了条件を基底条件と呼ぶ
• 再帰するたび終了条件へ近づく必要がある
• 階乗は再帰で表現できる
• 再帰呼出しではコールスタックが利用される
• 関数呼出しごとの情報をスタックフレームとして管理する
• 再帰が深すぎるとスタックオーバーフローの原因になる
• フィボナッチ数列は再帰で表現できるが、単純な実装では同じ計算が重複する
• 計算結果を保存して再利用する考え方をメモ化という
• 木構造は再帰的な構造を持つ
• DFSは再帰で実装できる
• クイックソートやマージソートでも再帰が利用される
• 分割統治法と再帰は相性がよい
• 再帰法では自分自身を呼び出す
• 反復法ではforやwhileなどのループを利用する
• 再帰は分かりやすさと効率が必ずしも一致しない
• 末尾再帰は再帰呼出しが関数の最後の処理になる形
• 再帰問題では「終了条件・引数の変化・戻るときの処理」を確認する

🍯 はちみつメモ

再帰は「自分に仕事をお願いして、終わったら戻ってくる」処理。お願いするたびにスタックへ仕事が積まれ、終了条件に到達すると今度は逆順に仕事が片付いていく。「どこで止まる？」「次の呼出しで何が変わる？」「戻るとき何をする？」の3つを見ると理解しやすい。