Pythonで再帰関数を使う方法！階乗・フィボナッチ数列の実装例

1. 再帰関数とは？自分自身を呼び出す関数の基本

1. 再帰関数とは？自分自身を呼び出す関数の基本

再帰関数とは、関数の中で自分自身を呼び出す関数のことです。プログラムの中で同じ処理を繰り返し使いたいときに使います。

でも、無限に呼び続けたらプログラムが止まらなくなるので、必ず「終了条件（ベースケース）」を用意して、その条件を満たしたら処理を終わるようにします。

2. 再帰関数の仕組みを簡単にイメージしよう

2. 再帰関数の仕組みを簡単にイメージしよう

たとえば、鏡の前に鏡を置いて鏡が無限に続くように見えるイメージがありますが、再帰関数は「自分を呼び出すけど、いつか終わる」という仕組みです。

具体的には、「自分で自分を呼ぶ」→「条件に当てはまればやめる」この繰り返しで成り立っています。

3. Pythonでの再帰関数の書き方

3. Pythonでの再帰関数の書き方

再帰関数は普通の関数とほとんど同じですが、関数の中で自分自身を呼び出すことがポイントです。次の例を見てみましょう。

def example(n):
    if n == 0:
        return "終了"
    else:
        return example(n-1)

この関数は、nが0になるまで自分自身を呼び続け、0になったら「終了」と返します。

4. 再帰関数でよく使う例①：階乗の計算

4. 再帰関数でよく使う例①：階乗の計算

階乗（かいじょう）とは、1からその数までの整数をすべてかけた値です。例えば、5の階乗は「5×4×3×2×1 = 120」です。

階乗は再帰関数で簡単に計算できます。次のコードを見てみましょう。

def factorial(n):
    if n == 0:
        return 1  # 0の階乗は1と決まっています
    else:
        return n * factorial(n - 1)

この関数は、自分自身を呼び出しながらnが0になるまで繰り返します。実際に計算してみましょう。

print(factorial(5))  # 120が出力されます

120

5. 再帰関数でよく使う例②：フィボナッチ数列の計算

5. 再帰関数でよく使う例②：フィボナッチ数列の計算

フィボナッチ数列は、最初の2つの数は1で、その後は前の2つの数の和になる数列です。例えば、1, 1, 2, 3, 5, 8, 13, ... となります。

再帰関数でフィボナッチ数列のn番目の値を求めるコードは次のようになります。

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

この関数も自分自身を2回呼び出しながら、nが1か2になったら1を返します。

print(fibonacci(7))  # 13が出力されます

13

6. 再帰関数を使うときの注意点

6. 再帰関数を使うときの注意点

• 終了条件（ベースケース）を必ず作る：ないと永遠に呼び続けてエラーになります。
• 深さに注意する：再帰が深くなりすぎると、プログラムが止まることがあります。
• 計算コストに注意：フィボナッチ数列の再帰は計算が多くなるので、大きな数字には向きません。

大きな数を計算したい場合は別の方法を使うか、工夫が必要です。

7. まとめ（※別記事にて）

7. まとめ（※別記事にて）

ここでは書きませんが、再帰関数は慣れるまで難しい部分もあります。基本の考え方と仕組みを理解して、少しずつ練習してみてください。

まとめ

まとめ

今回の記事では、Pythonにおける再帰関数（Recursive Function）の基礎から具体的な実装方法、そして注意点までを詳しく解説してきました。再帰関数は「自分自身を呼び出す」という、一見すると少し奇妙で魔法のようなプログラミング技法です。しかし、その正体は複雑な問題を小さな問題に分解して解く、非常に合理的で数学的なアプローチに基づいています。

再帰関数のポイントをおさらい

再帰をマスターするために、以下の3つのポイントを常に意識しましょう。これらを理解するだけで、コードの読みやすさとデバッグのしやすさが格段に向上します。

• ベースケース（終了条件）の定義： これがないと関数は永遠に自分を呼び続け、最終的には「RecursionError」を引き起こします。プログラムにおける「出口」を最初に設計することが、再帰を書く上での鉄則です。
• 再帰ステップ（自己呼び出し）： 問題を一段階小さくして自分を呼び出します。階乗であれば n を n-1 に、フィボナッチであれば n-1 と n-2 に分解していくプロセスです。
• メモリとスタックの意識： 再帰は呼び出しのたびにメモリ（スタック領域）を消費します。Pythonには標準で再帰の深さ制限があるため、非常に深い階層の処理にはループ（for文やwhile文）を検討する柔軟さも必要です。

実践的なサンプルプログラム：リストの合計値を求める再帰

記事で紹介した階乗やフィボナッチ数列以外にも、再帰は身近なところで活用できます。例えば、リストに含まれる数値の合計を、再帰を使って計算してみましょう。

def sum_list(numbers):
    # ベースケース：リストが空になったら0を返す
    if not numbers:
        return 0
    # 再帰ステップ：先頭の要素 ＋ 残りのリストの合計
    else:
        return numbers[0] + sum_list(numbers[1:])

# 実際に動かしてみる
my_list = [1, 2, 3, 4, 5]
result = sum_list(my_list)
print(f"リストの合計値は: {result}")

上記のコードを実行すると、次のような結果が得られます。

リストの合計値は: 15

このように、リストを「頭（最初の要素）」と「尻尾（それ以降）」に分けて考える手法は、関数型プログラミングの言語でもよく使われる非常に強力な考え方です。

再帰関数とSEO・アルゴリズムの密接な関係

プログラミング学習において、再帰関数の理解は避けては通れない道です。なぜなら、データの探索（木構造の走査）や、効率的な並び替え（クイックソートやマージソート）といった高度なアルゴリズムの多くが再帰を利用しているからです。検索エンジンのクローラーも、ウェブサイトのリンク構造を辿る際に、一種の再帰的な仕組みを用いて情報を収集しています。

また、コードの可読性を高めることは、開発チーム全体の生産性を向上させるだけでなく、保守性の高い高品質なソフトウェア開発に直結します。Pythonという直感的な言語を通じて再帰を学ぶことは、エンジニアとしての基礎体力を鍛える絶好の機会となるでしょう。