【Python】再帰関数の書き方を初心者向けに徹底解説！階乗・フィボナッチ・深さ制限まで

※このサイトの記事内では広告を掲載している場合があります。

関数を学んでいると「関数の中で自分自身を呼び出す」という不思議な書き方に出会います。これが再帰関数です。「頭がこんがらがる」「ループで書けばいいのでは？」と感じる方も多いのですが、仕組みさえつかめば怖くありません。

この記事では、Pythonの再帰関数の基本から、階乗・フィボナッチ数列などの定番例、再帰の深さ制限、ループとの使い分けまでを、初心者向けにやさしく解説します。関数の基本はPythonの関数（def）の作り方の記事も合わせてご覧ください。

再帰関数とは？

再帰関数とは、関数の内部で自分自身を呼び出す関数のことです。大きな問題を「同じ形の小さな問題」に分けて解くときに便利です。

再帰関数には、必ず次の2つが必要です。

終了条件（ベースケース）：これ以上自分を呼ばずに答えを返す条件
再帰呼び出し：問題を小さくして自分自身を呼ぶ部分

終了条件がないと、関数が永遠に自分を呼び続けてエラーになります。まずはカウントダウンで流れを確認しましょう。

def countdown(n):
    if n == 0:          # 終了条件
        print("発射！")
        return
    print(n)
    countdown(n - 1)    # 再帰呼び出し

countdown(3)
# 3
# 2
# 1
# 発射！

nが1ずつ減っていき、0になった時点で終了します。「小さくしながら呼ぶ」「いつか終了条件に届く」のが再帰の鉄則です。

定番例1：階乗を計算する

5の階乗（5! = 5×4×3×2×1）は、「n! = n × (n-1)!」という再帰的な性質を持っています。

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))   # 120
print(factorial(10))  # 3628800

factorial(5)は 5 * factorial(4) となり、さらに 4 * factorial(3) …と展開され、factorial(1)で1が返ると、順番に掛け算が戻ってきて120になります。

ループで書くとどうなる？

def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_loop(5))  # 120

同じ結果になります。単純な処理はループのほうが速く、読みやすいことも多いです。ループ処理の基本はwhile文の解説記事も参考になります。

定番例2：リストの合計を求める

def sum_list(nums):
    if not nums:             # 空リストなら0
        return 0
    return nums[0] + sum_list(nums[1:])

print(sum_list([1, 2, 3, 4, 5]))  # 15

「先頭の要素 + 残りの合計」と考えるのがポイントです。スライス（nums[1:]）で残りを取り出しています。実務では組み込みのsum()を使えば十分ですが、再帰の考え方を練習するには最適です。

ところで、独学でここまで進めて「自分のコードの書き方は合っているのだろうか」と不安になる方も多いと思います。そんなときは、プロに質問できる環境を検討するのも一つの手です。選び方はPythonが学べるプログラミングスクールの比較記事にまとめています。

定番例3：フィボナッチ数列

フィボナッチ数列は「前の2つの数を足して次の数を作る」数列（0, 1, 1, 2, 3, 5, 8, 13…）で、再帰の代表例です。

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

print(fib(10))  # 55

短く書けますが、実はこの書き方は同じ計算を何度も繰り返すため、nが大きくなると極端に遅くなります（fib(40)あたりで数十秒かかることも）。この問題はキャッシュで解決できます。

functools.lru_cacheで高速化

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(50))  # 12586269025

一度計算した結果を覚えておくので、一瞬で結果が返ります。デコレータ1行で高速化できるのはPythonの便利なところです。

定番例4：入れ子のリストを平らにする

リストの中にリストが入っているような「入れ子構造」は、再帰が最も活躍する場面です。深さが分からなくても対応できます。

def flatten(items):
    result = []
    for item in items:
        if isinstance(item, list):
            result.extend(flatten(item))  # リストなら再帰
        else:
            result.append(item)
    return result

print(flatten([1, [2, [3, 4]], 5]))  # [1, 2, 3, 4, 5]

リストの基本操作に慣れていない場合は、リスト内包表記の記事で復習しておくとスムーズです。

再帰の深さ制限に注意

Pythonには再帰の深さに上限があり、デフォルトでは約1000回です。超えるとRecursionErrorが発生します。

import sys
print(sys.getrecursionlimit())  # 1000

def infinite(n):
    return infinite(n + 1)

try:
    infinite(0)
except RecursionError:
    print("再帰が深すぎます")  # 再帰が深すぎます

sys.setrecursionlimit()で上限を変更できますが、上げすぎるとプログラムが異常終了する恐れがあります。深い再帰が必要な場合は、ループに書き換えるのが安全です。

再帰とループの使い分け

ループ向き：単純な繰り返し、回数が多い処理、速度やメモリを重視する場合
再帰向き：ツリー構造・入れ子構造・フォルダの階層など、問題が自然に「同じ形の小問題」に分かれる場合
注意：再帰は書き方が短くなる反面、終了条件のミスで無限再帰になりやすい

迷ったらまずループで書き、構造が入れ子で複雑になってきたら再帰を検討する、という順番がおすすめです。

よくあるエラーと対処法

RecursionError：終了条件が間違っている、または到達しない。引数が小さくなっているか確認しましょう。
戻り値を返し忘れる：再帰呼び出しの前にreturnが必要です（return n * factorial(n-1) など）。
結果がNoneになる：上記と同じく、return忘れが原因のことが多いです。

もっと効率的にPythonを学びたい人へ

再帰のような概念は、独学だと「なんとなく分かったつもり」で止まりがちです。つまずいたときにすぐ質問できる環境があると、理解のスピードが大きく変わります。マンツーマン指導で未経験からPythonを習得できるスクールもあるので、無料カウンセリングなどを活用して、自分に合うか確かめてみるのもよいでしょう。

※本記事には広告（アフィリエイトリンク）を含みます。

Pythonプログラミング｜マンツーマンレッスンで初めてをプロに育てる【Python Winner】

IT資格の取得でスキルを証明したい方は、Python3エンジニア認定基礎試験のおすすめ参考書の比較記事もぜひ参考にしてください。引数の扱いに不安がある方は*argsと**kwargsの解説も役立ちます。