自分を呼ぶ関数

関数の中で、自分自身を呼ぶ。それだけで再帰になるよ。

読みかたはこう。

• n が 0 なら答えは 1（かけ算の出発点）
• そうでなければ n かける「n - 1 の階乗」

kaijou の中に kaijou が出てくるのが気持ち悪いかもしれない。でも Python は気にしない。呼ばれた時点で中身が決まっていればいいからだよ。

ここがいちばん大事なところ。必ず「もう自分を呼ばない」場合を用意すること。これを ベースケース と呼ぶよ。

上の例では if n == 0: return 1 がそれだね。ここに来れば、それ以上は自分を呼ばずに終わる。

書き忘れるとどうなるか。永遠に自分を呼び続けて、Python が止めてくれるよ。

def kaijou(n):    return n * kaijou(n - 1)kaijou(5)

これを動かすと RecursionError: maximum recursion depth exceeded になる。「自分を呼ぶ深さが限界を超えた」という意味だよ。

再帰を書くときは、ベースケースから書く。これを習慣にしよう。

再帰は頭の中で追いにくい。だから第4章でやった print デバッグ の出番だよ。

関数の先頭で「いま n がいくつで呼ばれたか」を表示してみよう。だんだん小さくなって 0 で止まるのが見えるはずだ。

0 まで下がってから、こんどは逆向きに答えが組み上がっていく。1 → 1 → 2 → 6 の順だね。

正直に言うと、階乗も合計も for で書いたほうが読みやすい。下のリストの合計も、for で回して足すほうがずっと素直だよね。

それでも再帰を学ぶのは、この発想でしか書けない問題があるからだ。

もうひとつ、再帰には弱点がある。呼ぶたびに「どこまで進んだか」を Python が覚えておく必要があるので、深くなるとメモリを食うんだ。Python では千回ちょっとで打ち止めになるよ。

まず for で書けないか考える。書けないなら再帰。この順番でいいよ。

自分を呼ぶのは1回とは限らない。フィボナッチ数列は、前の2つを足していく数のならびだよ。

0, 1, 1, 2, 3, 5, 8, 13, ...

「n 番目は、n-1 番目と n-2 番目の和」。そのまま書けば再帰になるね。ベースケースは「2 より小さいならその数のまま」だよ。

これは再帰だからこそ短く書ける例。for で書くと、前の2つを覚えておく変数が要って少しごちゃつくんだ。

再帰がいちばん光るのは、中に同じものが入っているデータだよ。

フォルダの中のフォルダ、返信への返信、リストの中のリスト。こういう階層構造は、深さが決まっていないので for では回しきれない。2段なら二重ループ、3段なら三重ループ——では書ききれないよね。

下の hiraku は、入れ子のリストを平らにする関数だよ。中身がリストだったら自分を呼んでほどく、そうでなければそのまま足す。それだけで何段でも対応できる。

「深さを気にしなくていい」——これが再帰をわざわざ学ぶ理由だよ。