自分を呼ぶ関数：再帰：アルゴリズムとプログラミングのレッスン

入れ子の人形を開ける

入れ子になった人形は、開けると、中に少し小さい人形が入っています。それも開けると、さらに小さい人形です。

いちばん小さい人形が出たら、もう開けません。関数が自分自身を呼ぶ再帰も、これとそっくりな仕組みです。

このレッスンのゴール

メモ

自分自身を呼ぶ再帰の関数を、基本ケースを付けて書ける。

重要な言葉

ことば	いみ
再帰	関数が、自分自身を呼ぶこと
基本ケース	自分を呼ばずに、答えを返して止まる場合
再帰ケース	少し小さい問題で、自分を呼ぶ場合
コールスタック	呼び出し中の関数を、積み重ねて覚えておく場所
スタックオーバーフロー	呼び出しが深すぎて、覚える場所が足りなくなること

学生が入力するセルは、このプレビューでは空白です。

再帰には二つの場合がある

数を数えて 3、2、1、0 と言う手順を考えます。「0 なら言って止まる。そうでなければ言って、一つ小さい数でもう一度やる」と書けます。

止まる場合が基本ケース、もう一度やる場合が再帰ケースです。基本ケースがないと、永遠に止まりません。

カウントダウンの再帰

コード: python

def countdown(n):
    # まず今の数を言う
    print(n)
    # 基本ケース：0 なら何もせず、ここで止まる
    if n > 0:
        # 再帰ケース：一つ小さい数で、自分を呼ぶ
        countdown(n - 1)


countdown(3)
# 3 を 5 に変えて、何が出るか確かめましょう

階乗を再帰で書く

5の階乗は、5 × 4 × 3 × 2 × 1 で、120です。これは「5 × 4の階乗」とも言えます。

0の階乗は1と決めます。これが基本ケースです。n が0でなければ、n * fact(n - 1) を返します。

5の階乗を再帰で計算する

コマンド

docker exec jupyter python3 -c 'exec("def fact(n):\n    if n == 0:\n        return 1\n    return n * fact(n - 1)\nprint(fact(5))")'

ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。

呼び出しはコールスタックに積まれる

fact(3) は、fact(2) の答えが出るまで待ちます。fact(2) は fact(1) を待ちます。待っている呼び出しは、コールスタックに積み重なります。

基本ケースに着くと、答えが一番上から順に返っていき、待っていた掛け算が終わります。

例：fact(3) の呼び出し

段階	呼び出し	返す値
積む	fact(3) が fact(2) を呼ぶ	まだ待つ
積む	fact(2) が fact(1) を呼ぶ	まだ待つ
積む	fact(1) が fact(0) を呼ぶ	まだ待つ
底	fact(0)	1
戻る	fact(1) は 1 × 1	1
戻る	fact(2) は 2 × 1	2
戻る	fact(3) は 3 × 2	6

学生が入力するセルは、このプレビューでは空白です。

基本ケースがないと止まらない

基本ケースがない再帰は、呼び出しを積み続けます。積める数には限りがあり、超えるとエラーになって止まります。

次の実行で、Python が許す呼び出しの深さを見ます。見るだけで、何も壊れません。

許される深さを見る