記事内にはプロモーションが含まれています

Pythonの再帰関数とは？遅い場合の高速化や上限の確認方法も解説

Pythonの再帰関数とは？遅い場合の高速化や上限の確認方法も解説 プログラミングの疑問解決

プログラミングにおける「再帰関数」は、複雑な問題をシンプルに記述できる強力な手法であり、Pythonでも使われます。

しかし、「処理が遅い」「エラーで止まる」といったトラブルの種になることもあります。

「再帰関数を書いたら、処理が終わらないくらい遅くなってしまった…」
「RecursionError というエラーが出て、どう対処すればいいかわからない」

この記事では、上記のような悩みを解決するため、Pythonにおける再帰関数の基本的な仕組みから、処理速度を劇的に改善する「メモ化」のテクニック、そしてエラーの原因となる「再帰回数の上限」の確認・変更方法まで、実践的なノウハウを徹底解説します。

【著者プロフィール＆本記事の信頼性】
プロフィール
  • 著者は元エンジニア
  • 大手プログラミングスクールのWebディレクター兼 ライターを経験
  • 自らも地元密着型のプログラミングスクールを運営
⇒プロフィール詳細はコチラ
日本最大級の比較サイトで「4年連続人気NO.1」！
SNSでの評判の良さも圧倒的なプログラミングスクール『RUNTEQ（ランテック）』！
【RUNTEQの特徴】
✅受講生からの評判が驚くほど良い
✅学習はハードだが未経験とは思えないほど高いスキルが身に付く
✅挫折させない万全なサポート体制が用意されている
✅採用面接で担当者に刺さるレベルの高い「ポートフォリオ」を作成できる
✅給付金を使えば実質約13万円という格安料金で受講できる
当ブログ著者
当ブログ著者
忖度一切なしで、未経験から本気で
エンジニア転職を目指すならRUNTEQ一択です。

＼勧誘行為は一切なし！　相談だけでもOK！ ／

Pythonの再帰関数とは？

再帰関数とは、定義した関数の中で、自分自身を呼び出す関数のことを指します。

「大きな問題を、同じ構造を持つ小さな問題に分割して解く（分割統治法）」際によく用いられ、アルゴリズムの実装において非常に重要な役割を果たします。

再帰関数に必要な2つの要素

再帰関数を正しく動作させるためには、以下の2つの要素が不可欠です。
これらが欠けると、無限ループに陥ってしまいます。

ベースケース（終了条件）
再帰呼び出しをストップさせる条件です。
これがないと、関数は永遠に自分を呼び出し続けます。
（例）「引数が0になったら終了する」

再帰ステップ（再帰呼び出し）
問題を小さくしながら、自分自身を呼び出す処理です。
（例）「引数を1減らして、自分自身を呼び出す」

基本的な実装例：階乗の計算

最もシンプルな例として、「階乗（5! = 5 × 4 × 3 × 2 × 1）」を計算するプログラムを見てみましょう。

def factorial(n):
    # 1. ベースケース（終了条件）
    if n == 0:
        return 1
    
    # 2. 再帰ステップ（自分自身を呼び出す）
    return n * factorial(n - 1)

print(factorial(5))

実行結果は以下の通りです。

120

factorial(5) は 5 * factorial(4) を呼び出し、factorial(4) は 4 * factorial(3) を呼び出し……と続き、最終的に factorial(0) で 1 が返されることで、全ての計算が完了します。

再帰関数が「遅い」場合の高速化テクニック

再帰関数は数学的な定義をそのままコードに落とし込めるため可読性が高い一方、そのまま実装すると計算量が爆発的に増えて処理が遅くなることがあります。

その代表例が「フィボナッチ数列」です。

なぜ遅くなるのか？（フィボナッチ数列の例）

フィボナッチ数列（前の2つの数を足した数が、次の数になる数列）を、単純な再帰関数で実装してみます。

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

# 35番目の数を求めてみる（時間がかかる可能性があります）
print(fibonacci(35))

このコードを実行すると、nが30を超えたあたりから急激に計算が遅くなります。

理由は、「同じ計算を何度も重複して行っているから」です。

例えば fibonacci(5) を求めるには fibonacci(4) と fibonacci(3) が必要ですが、fibonacci(4) の中でもまた fibonacci(3) を計算します。

このように無駄な再計算が指数関数的に増えていくため、非常に非効率なのです。

高速化の鍵「メモ化（Memoization）」

再帰関数が遅くなってしまう問題を解決するのが「メモ化」という技術です。
一度計算した結果をメモリに保存しておき、2回目以降は再計算せずに保存された値を使います。

Pythonでは、標準ライブラリ functools の lru_cache デコレータを使うだけで、簡単にメモ化を実装できます。

from functools import lru_cache

# @lru_cacheをつけるだけで、自動的にメモ化（キャッシュ）される
# maxsize=None はキャッシュの上限を無制限にする設定
@lru_cache(maxsize=None)
def fibonacci_memo(n):
    if n <= 1:
        return n
    return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)

# メモ化なしでは時間がかかった計算も、一瞬で終わる
print(fibonacci_memo(35))
print(fibonacci_memo(100)) # もっと大きな数でも爆速

実行結果は以下の通りです。

9227465
354224848179261915075

@lru_cache を一行追加するだけで、計算速度が劇的に改善されました。
再帰関数を使っていて「遅い」と感じたら、まずはこのメモ化を検討してください。

再帰回数の上限（Recursion Limit）の確認と変更

再帰関数を使う上で避けて通れないのが、RecursionError です。

RecursionErrorとは？

関数を呼び出す際、コンピュータはメモリ上に「スタックフレーム」という領域を確保します。

再帰が深くなりすぎると、この領域を使い果たしてしまい（スタックオーバーフロー）、プログラムがクラッシュする危険があります。

Pythonでは安全のため、再帰呼び出しの深さに上限を設けており、これを超えると RecursionError: maximum recursion depth exceeded が発生します。

上限の確認方法

現在の再帰上限は、sys モジュールの getrecursionlimit() で確認できます。
多くの環境ではデフォルトで「1000」に設定されています。

import sys

limit = sys.getrecursionlimit()
print(f"現在の再帰上限: {limit}")

実行結果は以下の通りです。

現在の再帰上限: 1000

上限の変更方法

アルゴリズム上、どうしても深い再帰が必要な場合は、sys.setrecursionlimit() で上限を変更できます。

import sys

# 上限を2000に変更する
sys.setrecursionlimit(2000)
print(f"変更後の上限: {sys.getrecursionlimit()}")

# これまでエラーになっていた回数の再帰も実行可能になる
# （ただし、メモリの許容範囲内に限る）

ただし、注意点があります。

上限を上げればエラーは回避できますが、無限ループに近い再帰を行っている場合や、PCのメモリ容量を超えるような処理の場合、最終的にはPython自体がクラッシュして強制終了する可能性があります。

setrecursionlimit はあくまで「必要な深さが分かっている場合」の対処法であり、まずはアルゴリズム自体を見直して、ループ処理への書き換えなどができないか検討することを強く推奨します。

初心者がPythonの再起関数の使い方を効率的に学ぶには

Pythonの再起関数の使い方をはじめとするPythonのスキルを効率的に習得するには、プログラミングスクールの活用が最も近道です。

スクールでスキルを高めることにより、今の仕事に活かしたり、副業として高単価な案件を受注できたりするだけでなく、Pythonエンジニアとして転職することも可能になります。

Pythonエンジニアは需要が非常に高いため、それに比例して年収も高くなる傾向にあります。
「今よりも年収を上げたい」「将来性の高い職種であるエンジニアへ転職したい」といった気持ちが強い場合は、プログラミングスクールでPythonの専門スキルを習得しつつ、ポートフォリオ支援や転職支援を受けてエンジニアへ転職する、という道を目指すのもよいでしょう。

なお、「Pythonに強く、受講生からの評判も良いプログラミングスクール」には、以下のようなところがあります。

その他、以下の記事でもPythonのおすすめスクールをまとめていますので、興味のある方は是非参考にしてください。

【厳選】Pythonスクールおすすめ9選！オンラインで学べる安いプログラミングスクール
AI開発やデータ分析、Web開発など幅広い分野で活用されるPython。 需要が急増する中、効率的に学習できるプログラミングスクールを探している人も多いのではないでしょうか。 そこでこの記事では、2025年現在の「Pythonが学べるおすす...
progneer.net