再帰の練習

このページでは、手を動かして再帰呼び出しの動きを確かめます。

呼び出しの様子を表示する
#

再帰呼び出しのページでは、factorial(4) の計算をシミュレーションで追いかけました。同じことを、プログラム自身に表示させてみましょう。

次のプログラムを factorial_trace.py という名前で書いて、実行してください。 factorial に depth（呼び出しの深さ）という引数を足したものです。 depth はデフォルト引数で、最初に呼ぶときは省略でき、再帰呼び出しのたびに 1 増えます。 depth の分だけ空白を並べて、呼び出しの開始と返り値を表示しています。

def factorial(n, depth=0):
    indent = "  " * depth                       # 深さの分だけ字下げする。
    print(f"{indent}factorial({n}) 開始")
    if n == 0:
        result = 1
    else:
        result = n * factorial(n - 1, depth + 1)  # 1 段深く呼び出す。
    print(f"{indent}factorial({n}) -> {result}")
    return result

factorial(4)

実行すると、次のように表示されます。

factorial(4) 開始
  factorial(3) 開始
    factorial(2) 開始
      factorial(1) 開始
        factorial(0) 開始
        factorial(0) -> 1
      factorial(1) -> 1
    factorial(2) -> 2
  factorial(3) -> 6
factorial(4) -> 24

この表示を見ながら、次のことを確かめてください。

「開始」が 5 回続いてから、「->」が 5 回続きます。factorial(4) の答えが出るのは、一番最後です。なぜでしょうか。
factorial(2) -> 2 は、factorial(1) -> 1 の後に表示されます。factorial(2) は factorial(1) の答えが返ってくるまで、2 * ... の計算を待っているからです。
5 つの factorial は、それぞれ別の n を持っています（変数とスコープ）。字下げの深さが、どの n の話をしているかを表しています。

やってみよう
#

リストの合計を求める total 関数に、factorial と同じように depth を足して、total([3, 1, 4, 1, 5]) の呼び出しの様子を表示するプログラムを total_trace.py という名前で書いてください。実行結果は次のようになります。

total([3, 1, 4, 1, 5]) 開始
  total([1, 4, 1, 5]) 開始
    total([4, 1, 5]) 開始
      total([1, 5]) 開始
        total([5]) 開始
          total([]) 開始
          total([]) -> 0
        total([5]) -> 5
      total([1, 5]) -> 6
    total([4, 1, 5]) -> 10
  total([1, 4, 1, 5]) -> 11
total([3, 1, 4, 1, 5]) -> 14

🏁 解答例

def total(lst, depth=0):
    indent = "  " * depth
    print(f"{indent}total({lst}) 開始")
    if len(lst) == 0:
        result = 0
    else:
        result = lst[0] + total(lst[1:], depth + 1)
    print(f"{indent}total({lst}) -> {result}")
    return result

total([3, 1, 4, 1, 5])

壊れた再帰を直す
#

次の bug1.py〜bug4.py は、どれも間違った再帰関数です。それぞれについて、次の手順で取り組んでください。

プログラムをそのまま（間違ったまま）書いて実行し、何が起きるかを見る（エラーが出るなら、エラーメッセージの 最後の行 を読む）。
基底条件と再帰条件のどちらに問題があるかを考える。
直して、ファイルの末尾の assert が通るようにする。

bug1.py
#

def sum_to(n):
    """1 から n までの整数の合計を返す。"""
    return n + sum_to(n - 1)

assert sum_to(1) == 1
assert sum_to(10) == 55
print(sum_to(100))

ヒント

RecursionError: maximum recursion depth exceeded は、「再帰呼び出しが深くなりすぎた」というエラーです。 Python は、再帰呼び出しが約 1000 段を超えると、無限に続いているとみなして止めます。 sum_to(1)、sum_to(0)、sum_to(-1)、… と、どこまで進んでも止まる場所がありません。

🏁 解答例

def sum_to(n):
    """1 から n までの整数の合計を返す。"""
    if n == 0:          # 基底条件を追加した。
        return 0
    return n + sum_to(n - 1)

原因: 基底条件がなかった。

bug2.py
#

def power(x, n):
    """x の n 乗を返す。"""
    if n == 0:
        return 1
    return x * power(x, n)

assert power(2, 0) == 1
assert power(2, 10) == 1024
assert power(3, 3) == 27
print(power(2, 100))

ヒント

bug1.py と同じエラーが出ますが、原因は違います。基底条件（n == 0）はあります。では、再帰呼び出しの引数は基底条件に近づいているでしょうか。

🏁 解答例

def power(x, n):
    """x の n 乗を返す。"""
    if n == 0:
        return 1
    return x * power(x, n - 1)  # n を 1 減らして呼び出す。

原因: 再帰呼び出しの引数が基底条件に近づいていなかった（n が減っていない）。

bug3.py
#

def count_a(s):
    """文字列 s に含まれる文字 a の個数を返す。"""
    if s == "":
        return 0
    if s[0] == "a":
        1 + count_a(s[1:])
    else:
        count_a(s[1:])

assert count_a("") == 0
assert count_a("banana") == 3
assert count_a("python") == 0
print(count_a("abracadabra"))

ヒント

今度は TypeError です。エラーメッセージに NoneType とあるのは、どこかで None が返ってきたということです。関数は return がなければ None を返します（関数の返り値）。

🏁 解答例

def count_a(s):
    """文字列 s に含まれる文字 a の個数を返す。"""
    if s == "":
        return 0
    if s[0] == "a":
        return 1 + count_a(s[1:])  # return を追加した。
    else:
        return count_a(s[1:])      # return を追加した。

原因: 再帰呼び出しの結果を return していなかったので、None が返っていた。

bug4.py
#

def fib(n):
    """フィボナッチ数を返す。fib(0) = 0, fib(1) = 1, それ以降は直前の 2 つの和。"""
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

assert fib(1) == 1
assert fib(2) == 1
assert fib(10) == 55
print(fib(20))

ヒント

fib(1) は正しく動きますが、fib(2) で RecursionError になります。 fib(2) は fib(1) と fib(0) を呼び出します。fib(0) はどうなるでしょうか。基底条件は、再帰呼び出しが たどり着く全ての場合 を受け止める必要があります。

🏁 解答例

def fib(n):
    """フィボナッチ数を返す。fib(0) = 0, fib(1) = 1, それ以降は直前の 2 つの和。"""
    if n == 0:          # fib(0) の基底条件を追加した。
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

原因: fib(2) が呼び出す fib(0) を受け止める基底条件がなかった。if n <= 1: return n とまとめて書いてもよい。

再帰が止まらないときのチェックリスト
#

bug1.py〜bug4.py で見たように、再帰関数がうまく動かないときの原因はだいたい決まっています。自分の再帰関数が動かないときは、次の順に確かめてください。

RecursionError が出る
- 基底条件があるか（bug1.py）。
- 再帰呼び出しの引数は、基底条件に近づいているか（bug2.py）。
- 基底条件は、再帰呼び出しがたどり着く全ての場合を受け止めているか（bug4.py）。
答えが None になる、NoneType の TypeError が出る
- 再帰呼び出しの結果を return し忘れていないか（bug3.py）。

やってみよう: リストの最大値
#

最後に、自分で再帰関数を書いてみましょう。次のプログラムを maximum.py という名前で書き、maximum 関数を 再帰呼び出しを用いて 完成させてください。リストの合計と同じように、「先頭の要素」と「残りの部分の最大値」を比べれば求められます。基底条件は何になるか、まず考えてください（空のリストに最大値はありません）。

def maximum(lst):
    """リスト lst（要素が 1 つ以上）の最大値を返す。"""
    # ここを再帰呼び出しを用いて実装してください。
    pass

assert maximum([5]) == 5, "要素が 1 つなら、それが最大値"
assert maximum([3, 1, 4, 1, 5]) == 5
assert maximum([1, 2, 3]) == 3, "最後の要素が最大値のとき"
assert maximum([-3, -1, -2]) == -1, "負の数だけのとき"
print(maximum([3, 1, 4, 1, 5, 9, 2, 6]))

うまく動かないときは、上のチェックリストを見直すか、factorial のときのように depth を足して呼び出しの様子を表示してみてください。

🏁 解答例

def maximum(lst):
    """リスト lst（要素が 1 つ以上）の最大値を返す。"""
    if len(lst) == 1:               # 要素が 1 つなら、それが最大値（基底条件）。
        return lst[0]
    rest_max = maximum(lst[1:])     # 残りの部分の最大値。
    if lst[0] > rest_max:           # 先頭の要素と比べて、大きい方を返す。
        return lst[0]
    else:
        return rest_max

assert maximum([5]) == 5, "要素が 1 つなら、それが最大値"
assert maximum([3, 1, 4, 1, 5]) == 5
assert maximum([1, 2, 3]) == 3, "最後の要素が最大値のとき"
assert maximum([-3, -1, -2]) == -1, "負の数だけのとき"
print(maximum([3, 1, 4, 1, 5, 9, 2, 6]))

最後の if 〜 else は、組み込み関数の max を使って return max(lst[0], maximum(lst[1:])) と 1 行に書くこともできます。

なお、この maximum に空のリストを渡すと RecursionError になります。なぜそうなるのか、bug4.py と見比べて考えてみてください。

呼び出しの様子を表示する#

やってみよう#

壊れた再帰を直す#

bug1.py#

bug2.py#

bug3.py#

bug4.py#

再帰が止まらないときのチェックリスト#

やってみよう: リストの最大値#

呼び出しの様子を表示する
#

やってみよう
#

壊れた再帰を直す
#

bug1.py
#

bug2.py
#

bug3.py
#

bug4.py
#

再帰が止まらないときのチェックリスト
#

やってみよう: リストの最大値
#