教科書で再帰関数のページを開いて、数行読んだところで頭がこんがらがった。関数が自分自身を呼ぶという説明の意味が、どうしてものみ込めない。
Pythonを学んでいる方から、この相談は本当によく届きます。
そしてもうひとつ多いのが、再帰を書いてみたら RecursionError という見慣れないエラーで止まった、という話です。
この記事では、再帰関数の考え方を日常の場面にたとえながら、エラーの直し方や実務での使いどころまでを順番にほどいていきます。
再帰関数は、自分自身を呼び出す関数のこと¶
まずは言葉の意味から確認しましょう。再帰関数とは、処理の途中で自分自身をもう一度呼び出す関数のことです。
英語では recursion といいます。くり返し戻ってくる、という意味の言葉です。
ふつうの関数は、別の関数を呼んで結果を受け取ります。再帰関数がやっているのも同じことで、たまたま呼び出す相手が自分だった、というだけの話です。
言葉だけだと不思議に聞こえるので、いちばん小さな例を動かしてみましょう。3から0までカウントダウンするだけのコードです。
def countdown(n):
if n == 0: # ここで止まる
print("発射！")
return
print(n)
countdown(n - 1) # 自分をもう一度呼ぶ
countdown(3)
実行すると、3、2、1と表示されてから発射と出ます。countdown(3) の中で countdown(2) が呼ばれ、その中で countdown(1) が呼ばれ、と数珠つなぎに続いていくからです。
階段を1段ずつ降りるイメージで考える¶
再帰がつかみにくいのは、頭の中で全部を同時に追いかけようとするからだと思います。
おすすめは、階段を降りる場面を想像することです。あなたは3段目に立っていて、やることは2つだけ。今いる段の番号を声に出し、1段下に降りる。
これを降りる人が自分でくり返せば、勝手に1段目まで到達します。ぜんぶの段を一度に見渡す必要はありません。
再帰関数の読み方も同じで、いま呼ばれた1回分だけを見れば十分です。再帰は、全体を追うのではなく1回分だけを正しく書けばいい仕組みです。
終了条件がないと、プログラムは止まらなくなる¶
さきほどのコードで、いちばん大事な行はどこだと思いますか。
答えは if n == 0: の部分です。これがないと、countdown は永遠に自分を呼び続けます。
この止まるための条件を、ベースケースと呼びます。再帰の出口にあたる部分です。
試しに、出口を消すとどうなるかを見てみましょう。実際に手元で動かしてみると、再帰の怖さと安全装置の両方が一度に理解できます。
def countdown(n):
print(n)
countdown(n - 1) # 出口がない
countdown(3)
これを走らせると、数字が延々と流れたあとで RecursionError: maximum recursion depth exceeded というエラーが出て止まります。
無限に動き続けてパソコンが固まるのではなく、Pythonがある深さで打ち切ってくれるわけです。この打ち切りが、次の話につながります。
RecursionErrorが出たときに見るべき場所¶
RecursionError は、再帰の深さが上限を超えたときに出るエラーです。Pythonには、関数呼び出しをどこまで積み重ねてよいかの上限があらかじめ決まっています。
その上限は、標準ライブラリの sys モジュールで確認できます。
import sys
print(sys.getrecursionlimit()) # 多くの環境で 1000
多くの環境では1000が返ってきます。つまり、関数の呼び出しが1000段ほど積み上がった時点で、Pythonは危険と判断して手を止めるということです。
この上限は、暴走した再帰がインタプリタごとクラッシュするのを防ぐための安全装置です。公式ドキュメントにも、C言語レベルのスタックがあふれるのを避けるためだと書かれています。
上限を上げる前に、まず設計を疑う¶
sys.setrecursionlimit() を使えば、この上限は変えられます。ただし、エラーを見た瞬間にこれへ手を伸ばすのはおすすめしません。
私は10年ほどエンジニアとして開発に関わってきましたが、RecursionError の原因がほんとうに深さ不足だったケースは、記憶にある限り数えるほどです。
実際に多いのは、ベースケースの書き間違いです。以前、データの階層をたどる処理で、親をたどるつもりが自分自身を返す行が混ざっていて、無限ループになっていたことがありました。上限を上げていたら、気づくのが半日は遅れていたと思います。
エラーを見たら、まずこの順番で確認するのが安全です。
| 確認すること | 見るポイント |
|---|---|
| 出口はあるか | ベースケースの if を書いたか |
| 出口に到達するか | 引数がちゃんと出口の値へ近づいているか |
| 同じ値で呼んでいないか | f(n) の中で f(n) を呼んでいないか |
| 本当に1000段必要か | データの構造がそこまで深いのか |
上限を上げるのは、この4つを確認したあとの最後の手段です。高くしすぎるとPythonごと落ちる可能性があるので、公式ドキュメントも慎重に扱うよう注意しています。
なお、エラーの読み方そのものに不安がある方は、【関連記事】Pythonのエラー文はどこを読めばいい？初心者向けtracebackの見方もあわせて読んでみてください。
再帰とループ、どちらで書けばいいのか¶
ここまで読んで、こう思った方もいるはずです。カウントダウンなら for や while で書けばいいのでは、と。
そのとおりです。さきほどの例に限れば、ループのほうが読みやすくて速い。
判断の基準はシンプルで、扱うデータが一直線に並んでいるか、それとも入れ子になっているかで決まります。
| データの形 | 向いている書き方 | 具体例 |
|---|---|---|
| 一直線に並んでいる | ループ | リストの集計、1から100までの合計 |
| 入れ子になっている | 再帰 | フォルダの中のフォルダ、辞書の中の辞書 |
| 回数が決まっていない | ループ | 入力が正しくなるまで聞き直す |
| 同じ形が中に現れる | 再帰 | 組織図、コメントの返信ツリー |
くり返し処理そのものを整理したい方は、Pythonのwhile文とは？条件が真の間くり返す基本と無限ループの止め方で、ループ側の考え方をまとめています。
入れ子構造を扱うとき、再帰は本当に強い¶
再帰の本領が出るのは、同じ形が中にもう一度現れるデータです。いちばん身近なのは、パソコンのフォルダでしょう。
フォルダの中にはファイルとフォルダがあり、そのフォルダの中にもまたファイルとフォルダがある。この説明自体が、すでに再帰の形をしています。
こういうデータをループだけで書こうとすると、何重ものネストか、自前の待ち行列が必要になります。再帰なら、1階層分の処理を書くだけで済みます。
pathlib を使って、フォルダの中のPythonファイルをすべて数える例を見てみましょう。
from pathlib import Path
def count_py(folder):
total = 0
for item in folder.iterdir():
if item.is_dir():
total += count_py(item) # フォルダなら中へ潜る
elif item.suffix == ".py":
total += 1 # ファイルなら数える
return total
print(count_py(Path("myproject")))
注目してほしいのは、この関数が階層の深さをいっさい気にしていない点です。3階層でも10階層でも、同じコードがそのまま動きます。
再帰は、深さが決まっていないデータを、深さを意識せずに書くための道具です。 ファイルパスの扱いに慣れていない方は、Pythonのpathlibとは？ファイルパス操作を初心者向けに解説を先に読むと理解が早くなります。
木構造という言葉に身構えなくていい¶
こうした入れ子のデータは、専門的には木構造と呼ばれます。枝分かれしながら広がる形が、木を逆さにしたように見えるからです。
名前はいかめしいですが、中身はさきほどのフォルダと同じです。組織図、HTMLのタグ、コメントの返信、どれも木構造の仲間になります。
木構造が出てきたら再帰を思い出す。この対応づけを覚えておくだけで、書けるコードの幅がぐっと広がります。
素直な再帰が遅いとき、キャッシュで一気に速くなる¶
再帰には落とし穴もあります。書き方によっては、とんでもなく遅くなるのです。
有名な例が、フィボナッチ数列です。前の2つの数を足していく数列で、教科書では必ず再帰の題材に選ばれます。
素直に書くと、次のようになります。定義をそのまま写しただけの、とても読みやすいコードです。
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(30)) # 832040
これが動くことは動くのですが、fib(30) を求めるだけで関数が約269万回も呼ばれます。同じ計算を何度もやり直しているからです。
fib(5) を計算する途中で fib(3) が2回、fib(2) が3回登場する。この重複が、深くなるほど雪だるま式にふくらんでいきます。
lru_cacheを1行足すだけで、呼び出しが31回になる¶
救いは、この問題が標準ライブラリだけで解けることです。functools の cache を関数の上に置くだけで済みます。
from functools import cache
@cache
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(30)) # 832040
一度計算した答えを覚えておき、同じ引数で呼ばれたら計算せずに返す。この仕組みをメモ化と呼び、遅い再帰を救う定番の手当てになっています。
先ほど約269万回だった関数呼び出しは、これで31回になります。コードの見た目はほとんど変わっていないのに、です。
cache はPython 3.9で追加された、上限のないキャッシュです。古いバージョンや、メモリの使用量を抑えたい場面では lru_cache を使います。
| デコレータ | 特徴 | 使いどころ |
|---|---|---|
@cache |
上限なし。3.9以降で使える | 引数の種類が限られているとき |
@lru_cache |
既定では128件まで覚える | 引数が無数にありうるとき |
@lru_cache(maxsize=None) |
上限なし。3.8以前の書き方 | 古い環境で cache の代わりに |
functools のほかの道具も気になった方は、Pythonのfunctoolsとは？lru_cacheやpartialで関数を速く短くする使い方で全体像を紹介しています。
なぜ再帰が遅くなるのかを数の側から理解したい方には、実行時間が終わらないを卒業する！コードを100倍速くする計算量の考え方もおすすめです。
実務で再帰を書くときに気をつけていること¶
最後に、現場で再帰を使うときの勘どころを共有します。どれも、失敗して覚えたことばかりです。
ひとつめは、出口を先に書くことです。関数の1行目にベースケースを置いてから、残りを書き始める。この順番にしてから、無限再帰をほとんど作らなくなりました。
ふたつめは、深さの見積もりです。扱うデータが数千段の深さになりうるなら、再帰ではなくループと自前の待ち行列で書き直したほうが安全です。
みっつめは、外部から来るデータへの警戒です。ユーザーが投稿したコメントツリーのように、深さを自分で決められないデータでは、深さの上限を引数で持たせて途中で打ち切るようにしています。
再帰は、読みやすさと引き換えに深さのリスクを抱える書き方です。 そのリスクを見積もれるかどうかが、使ってよい場面かどうかの分かれ目になります。
まとめ：1回分だけを正しく書けばいい¶
再帰関数の要点を、あらためて振り返っておきましょう。
自分自身を呼び出す関数が再帰関数で、必ず出口となるベースケースが要る。出口を忘れると RecursionError で止まり、その上限は多くの環境で1000段です。
一直線のデータはループ、入れ子のデータは再帰。そして素直な再帰が遅いときは、@cache を1行足すだけで劇的に速くなることがあります。
最初から全部を追いかけようとせず、いま呼ばれた1回分だけを見る。この読み方に慣れれば、再帰はぐっと身近な道具になります。
まずはこの記事のカウントダウンを写して動かし、数字を変えて挙動を眺めてみてください。手を動かした分だけ、頭の中のもつれはほどけていきます。
ここまでお読みいただきありがとうございました。
