フィボナッチで学ぶ再帰の概念 失敗しないコツと例

再帰は関数が自分自身を呼び出す考え方です。

フィボナッチ数列は定義がシンプルで、再帰の練習題材として最適です。

本記事では、ベースケースの決め方から手で追う確認方法まで、失敗しないコツと具体例でやさしく説明します。

再帰の概念をフィボナッチで学ぶ

再帰とは

再帰とは、問題を同じ形のより小さな問題に分けて、自分自身の関数を呼び出して解く方法です。

関数が自分を呼ぶため、終わりを決める条件が必須になります。

これを一般にベースケースや停止条件と呼びます。

停止条件に達しないと無限再帰になり、プログラムが止まらなくなります。

再帰は、問題の定義が「自分自身を使って説明される」タイプのときに読みやすく書けるのが特徴です。

再帰の2本柱

ベースケースと、引数を小さくしてベースケースに近づける工夫の2点が、再帰の肝です。

ベースケースに該当するときはすぐに答えを返し、それ以外は一歩小さい引数で自分を呼び出して結果を組み立てます。

フィボナッチ数列の定義

フィボナッチ数列は、前の2つの値の和で次の値を作ります。

もっとも広く使われる定義は次の通りです。

f(0)=0、f(1)=1、f(n)=f(n-1)+f(n-2)(n≥2) です。

小さな値の一覧

最初のいくつかを確認すると流れがつかみやすいです。

再帰関数の基本形

再帰関数は「ベースケースを先に判定して返す」→「それ以外は小さくした引数で自分を呼ぶ」の順に書きます。

def func(n):
    # 1. ベースケース
    if 条件を満たす:
        return 答え
    # 2. 小さくした引数で再帰呼び出し
    smaller = func(nを小さくしたもの)
    # 3. 再帰結果から答えを作る
    return smallerを使って答えを作る

注意点

毎回、少なくともどちらかの引数が必ず小さくなるようにします。

そうしないとベースケースへ到達できず、停止しません。

再帰が向く理由

フィボナッチは「次の値が直前2つの和」という自己参照の定義なので、定義がそのままコードに写せるのが利点です。

コードが短く直感的になり、数学的な意味を保ったまま表現できます。

ただし、素朴な再帰は計算の重複が多くて遅くなりがちです。

学ぶには最適ですが、大きなnでは工夫が必要です。

フィボナッチを再帰で書く手順

ベースケースを決める

f(0)とf(1)を決めることが最初の一歩です。

標準的には f(0)=0、f(1)=1 とします。

ここが明確なら、nが0か1に当たったとき即座に戻れます。

ベースケースを先に考える理由

ベースケースがないと、どんなにきれいな再帰式でもプログラムは止まりません。

「止めるための出口」を先に作ると覚えると良いです。

再帰式を書く(f(n)=f(n-1)+f(n-2))

f(n)は、1つ前と2つ前の結果を足せば良いので、コードでは2回の再帰呼び出しが登場します。

nを必ず小さくして呼び出すため、nはn-1やn-2になります。

再帰の重複に触れておく

例えばf(5)を計算するときf(3)を何度も計算します。

これが遅さの原因です。

後ほど対処法を紹介します。

再帰関数の形

ここまでの内容を組み合わせると、次の形になります。

def fib(n):
    # 0. 不正な入力のガード
    if n < 0:
        raise ValueError("nは0以上にしてください")
    # 1. ベースケース
    if n == 0:
        return 0
    if n == 1:
        return 1
    # 2. 再帰式
    return fib(n - 1) + fib(n - 2)

ベースケースが先、次に再帰式という順番を守ると読みやすく安全です。

小さな確認

fib(0)=0、fib(1)=1、fib(2)=1 になっているかを最初に確かめます。

ここがズレていると後の値がすべてズレます。

再帰関数の例

より丁寧なメッセージや型の確認を追加したバージョンです。

def fib(n):
    if not isinstance(n, int):
        raise TypeError("nは整数で指定してください")
    if n < 0:
        raise ValueError("nは0以上にしてください")

    if n == 0:
        return 0
    if n == 1:
        return 1

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

初心者のうちは、入力チェックを入れて「予想外の使われ方」を早めに発見できるようにしておくと安心です。

呼び出しの例を手で追う

n=4を例に、どの順番で呼ばれるかを紙に書いて追ってみます。

手で追うと、ベースケースに確実に到達できることや、どこで足し合わせているかが見えるようになります。

fib(4)
= fib(3) + fib(2)
= (fib(2) + fib(1)) + (fib(1) + fib(0))
= ((fib(1) + fib(0)) + 1) + (1 + 0)
= ((1 + 0) + 1) + (1 + 0)
= (1 + 1) + 1
= 3

簡易トレースの出力イメージ

次のようにインデントを使って深さを表示すると流れがつかめます。

def fib_trace(n, depth=0):
    print("  " * depth + f"fib({n}) を呼び出し")
    if n < 2:
        print("  " * depth + f"→ {n}")
        return n
    r = fib_trace(n - 1, depth + 1) + fib_trace(n - 2, depth + 1)
    print("  " * depth + f"→ {r}")
    return r

fib_trace(4)

出力を目で追うと、どこで分岐し、どこで値が返ってくるかが直感的に理解できます。

失敗しないコツ

停止条件を必ず書く

停止条件がない再帰は必ず失敗します。

PythonではRecursionErrorが発生します。

フィボナッチならn==0とn==1で即返す、という形を最初に書いてから再帰式を書くと安全です。

よくある見落とし

条件式の比較演算子を間違えると止まりません。

例としてn<=1でまとめるとシンプルです。

if n <= 1:
    return n

引数を小さくして近づける

再帰呼び出しのたびに、引数がベースケースへ必ず近づくようにします。

フィボナッチではn-1とn-2に分解するため、1歩か2歩ずつ確実に小さくなります。

近づかない例

n+1のように大きくする呼び出しは論外です。

必ず減らしましょう。

ベースケースを先に置く

関数の先頭にベースケースを置くと、読み手にも自分にも親切です。

早期returnにより、無駄な呼び出しを避け、バグの混入も減らせます。

先に置かないと起きること

再帰式が先だと、意図しない評価順で無限再帰に入る可能性があります。

0と1の扱いを統一する

f(0)とf(1)の定義をチームや自分のノートで明文化して統一します。

書籍によってはf(1)=1、f(2)=1をベースケースにする流儀もあります。

どちらでも構いませんが、コード・テスト・コメントで一貫させます。

例: 2つの流儀

• 0始まり流儀: f(0)=0、f(1)=1
• 1始まり流儀: f(1)=1、f(2)=1

小さな入力でテスト

最初はn=0、1、2、5など小さな値で正しい結果を確認します。

手で計算できる範囲で確かめると、定義のズレや入力チェックの不備にすぐ気づけます。

期待値の一覧

簡単な表を用意して比べると便利です。

printでトレース

デバッグ時はprintで「どの引数で呼ばれ、何を返したか」を出すと理解が進みます。

depthを渡してインデントすると見やすくなります。

トレースは学習には有効ですが、実運用では外しましょう。

再帰の深さに注意

Pythonは再帰の深さに上限があります(おおよそ1000程度)。

大きいnを素朴な再帰で計算すると、深すぎてエラーになることがあります。

sys.setrecursionlimitで変更もできますが、安易に増やすのではなく、ループやメモ化で解決するのが安全です。

よくあるつまずきと簡単な対処

ベースケース不足で止まらない

原因は単純で、止める条件がありません。

次のような誤りに注意します。

# 悪い例: ベースケースがない
def fib_bad(n):
    return fib_bad(n - 1) + fib_bad(n - 2)

修正はn<=1で即返すことです。

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

nが負になるバグ

入力チェックを入れ、最初に不正値をはじくと安全です。

def fib(n):
    if not isinstance(n, int):
        raise TypeError("整数を指定してください")
    if n < 0:
        raise ValueError("nは0以上にしてください")
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

定義のズレで結果が違う(f(0)=0か1か)

流儀の違いによるズレは珍しくありません。

0始まりと1始まりで、同じnでも値が違うことがあります。

プロジェクトの最初にどちらを採用するかを決め、テストの期待値も合わせます。

ずれに気づくヒント

f(2)の値が1になるかどうかで見分けられます。

0始まりならf(2)=1、1始まりならf(2)=1ですが、インデックス解釈が異なります。

計算が遅い時の対処

素朴な再帰は同じ値を何度も計算してしまうため、呼び出し回数が急増して遅くなります。

対処法は主に2つです。

1) メモ化(結果の記憶)

一度計算した結果を辞書に保存して再利用します。

初心者にも扱いやすい方法です。

memo = {0: 0, 1: 1}

def fib_memo(n):
    if n in memo:
        return memo[n]
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]

2) ループで書き直す

前から順に足していけば重複計算がありません。

def fib_loop(n):
    if n < 0:
        raise ValueError("nは0以上にしてください")
    a, b = 0, 1  # aがf(0)、bがf(1)
    for _ in range(n):
        a, b = b, a + b
    return a  # ここがf(n)

スピード重視ならループ、分かりやすさ重視の学習なら再帰と使い分けると良いです。

ループ版との違い

ループ版は関数呼び出しのオーバーヘッドがなく、高速かつメモリ使用量が一定です。

再帰版は定義に忠実で読みやすい一方、深さの制限や速度で不利になる場面があります。

どちらも正解なので、目的に合わせて選ぶことが大切です。

まとめ

再帰の本質は「ベースケース」と「小さくして近づける」の2点に集約されます。

フィボナッチ数列はこの2点を練習する題材として最適で、定義をそのままコードに落とし込めます。

まずはf(0)とf(1)を明確に決め、n<=1で返す形を先に書き、n-1とn-2へ小さく分解する基本を守りましょう。

計算が遅いと感じたら、メモ化やループ版に切り替えるだけで実用レベルになります。

最後に、printのトレースで手を動かして確認する習慣を付けると、再帰に対する不安は自然と消えていきます。