再帰関数の応用例

INDEX

再帰関数の応用例
まとめ

関数の中で自分自身を呼び出す仕組みである「再帰関数」。一見すると奇妙な処理の流れに見えますが、数学的な定義をそのままプログラムに落とし込めるため、複雑な問題を驚くほどシンプルに分割・解決できる強力な武器になります。

本記事では、アルゴリズムの学習や実務のプログラミングコンテストでもよく登場する、実践的な再帰関数の応用例を3つ紹介します。それぞれの仕組みと、初心者がつまずきやすいポイントを学びましょう。

応用例 1: フィボナッチ数列

フィボナッチ数列とは、「前の2つの項を足すと、次の項になる」というルールで並ぶ数式（1, 1, 2, 3, 5, 8, 13...）のことです。数学的な数式（$F(n) = F(n-1) + F(n-2)$）の構造そのものが再帰的なため、コードへの落とし込みが非常に直感的になります。

# フィボナッチ数列の第n項を再帰で計算する関数
def fibonacci(n):
    # ベースケース（再帰のストップ条件）
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    # 自分自身を2回呼び出して足し合わせる（再帰ステップ）
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))  # 出力: 55

上記のコードの構成要素と注意点は以下の通りです。

if n <= 0: および elif n == 1:：再帰呼び出しをストップさせる「ベースケース」です。これがないと無限に自分を呼び出し続け、プログラムがクラッシュします。
fibonacci(n - 1) + fibonacci(n - 2)：より小さな問題へと分解して再計算しています。

つまずき注意：このコードの効率の罠
このシンプルなコードは、n が大きくなると一気に処理が重くなります。たとえば fibonacci(5) を計算するために fibonacci(4) と fibonacci(3) を呼び出しますが、その先でも同じ fibonacci(3) の計算が何度も重複して実行されるためです。実務で大きな数値を扱う場合は、一度計算した結果を保存しておく「メモ化」というテクニックと組み合わせるのが鉄則です。

応用例 2: ユークリッドの互除法

ユークリッドの互除法は、2つの整数の「最大公約数（GCD）」を求めるための古くから知られる効率的なアルゴリズムです。「$a$ を $b$ で割った余りを $r$ としたとき、$a$ と $b$ の最大公約数は、$b$ と $r$ の最大公約数に等しい」という性質を再帰で表現します。

# 再帰を使ったユークリッドの互除法
def gcd(a, b):
    # 余りが0になった時点で、その時のb（割り切った数）が最大公約数
    if b == 0:
        return a
    else:
        # aにbを、bに余り（a % b）を渡して再帰呼び出し
        return gcd(b, a % b)

print(gcd(48, 18))  # 出力: 6

上記のコードにおける動作は以下の通りです。

gcd(48, 18) が呼ばれると、48 % 18 の余り 12 が計算され、次は gcd(18, 12) が呼ばれます。
18 % 12 の余り 6 が計算され、次は gcd(12, 6) が呼ばれます。
12 % 6 は余り 0 なので、次の呼び出し gcd(6, 0) で b == 0 が成立し、6 が返されます。

応用例 3: ハノイの塔

ハノイの塔は、3本の柱（A, B, C）を使って、サイズがすべて異なるディスクをルールに従って別の柱へすべて移動させる有名なパズルです。「大きなディスクの上に小さなディスクを置いてはならない」という制約があります。一見複雑ですが、「$n-1$ 枚のディスクを一時的な柱に退避させ、一番大きいディスクを目的地に動かし、退避させていた $n-1$ 枚をその上に乗せる」という風に問題を切り分けると、再帰で驚くほど短く書くことができます。

# ハノイの塔を解く関数
# n: ディスクの枚数、source: 移動元、target: 移動先、auxiliary: 作業用の柱
def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"ディスク1を {source} から {target} へ移動")
        return

    # ステップ1: 一番下以外のn-1枚を、移動元から作業用の柱へ移動
    hanoi(n - 1, source, auxiliary, target)

    # ステップ2: 一番大きなディスクを移動元から目的地へ移動
    print(f"ディスク{n}を {source} から {target} へ移動")

    # ステップ3: 作業用の柱に退避させていたn-1枚を目的地へ移動
    hanoi(n - 1, auxiliary, target, source)

# 3枚のディスクをAからCへ、Bを作業用として移動させる
hanoi(3, 'A', 'C', 'B')

このコードを実行すると、パズルを解くための具体的な手順が全ステップ自動でコンソールに出力されます。人間が考えると頭が混乱する手順も、再帰を使えば数行のロジックだけで解決可能です。

再帰関数のメリットとデメリット

再帰関数は万能ではありません。ループ（for 文や while 文）と比較した際の特徴をしっかりと把握して使い分ける必要があります。

メリット（得意なこと）	デメリット（苦手なこと）
木構造の探索（フォルダ階層の調査など）や、数学的定義のアルゴリズムを圧倒的にシンプルかつ少ない行数で記述できる。	関数を呼び出すたびにメモリ（スタック領域）を消費するため、再帰の回数が多すぎると `RecursionError`（メモリ不足）を引き起こす。
`for` 文の多重ループでは表現しきれない、動的に深さが変わるパズルや探索問題を直感的に書ける。	フィボナッチ数列の例のように、工夫なしで書くと全く同じ計算を何度も繰り返してしまい、処理速度が急激に低下する罠がある。

まとめ

再帰関数の応用における重要ポイントは以下の通りです。

ベースケース（終了条件）を絶対に見失わない：再帰を止める条件の記述漏れや条件のミスは、プログラムが止まらなくなる無限ループのバグを引き起こします。
複雑な問題を「1つ手前までの問題」に分解する：ハノイの塔やフィボナッチ数列のように、全体のルールを「小さな同じ形の処理」に切り分ける設計思考が求められます。
メモリ消費と実行速度のトレードオフを意識する：コードがシンプルになる反面、スタックメモリの消費や無駄な重複計算が発生しやすいため、状況に応じてループ処理への書き換えやメモ化を検討する必要があります。

再帰関数を使いこなせるようになると、データ構造（ツリー構造やグラフ構造）の操作など、一歩進んだ高度なプログラミングがスムーズに実装できるようになります。