再帰とは、関数が自分を呼ぶこと
再帰とは、関数が自分自身を呼び出して、問題を小さくしていく書き方です。階乗や、フォルダの中のフォルダをたどる処理に使います。
うまく書けば、長いループが数行になります。止まる場所を忘れると、永久に続きます。
このレッスンのゴール
メモ
基底ケースを決めて、再帰で階乗や合計を求める関数を書ける。
重要な言葉
| ことば | いみ | れい |
|---|---|---|
| 再帰 | 関数が、自分自身を呼ぶこと | |
| 基底ケース | 自分を呼ばずに、答えを返して止まる場合 | n が 1 以下 |
| 再帰ケース | 少し小さい問題で、自分を呼ぶ場合 | |
| コールスタック | 呼び出し中の関数を、積み重ねて覚える場所 | |
| 階乗 | 1 から n までの整数を、全部掛けた数 | 5 の階乗は 120 |
学生が入力するセルは、このプレビューでは空白です。
大きな問題を小さな問題に変える
5 の階乗は、5 かける 4 の階乗です。4 の階乗は、4 かける 3 の階乗です。同じ形の、少し小さな問題になっています。
これを 1 の階乗まで続けると、答えが 1 と決まります。そこから掛け算を戻していきます。
階乗を呼び出しの順に追う
| 呼び出し | 自分を呼ぶか | 返す値 |
|---|---|---|
| factorial(4) | 呼ぶ、factorial(3) | 4 かける 6 で 24 |
| factorial(3) | 呼ぶ、factorial(2) | 3 かける 2 で 6 |
| factorial(2) | 呼ぶ、factorial(1) | 2 かける 1 で 2 |
| factorial(1) | 呼ばない | 1 |
学生が入力するセルは、このプレビューでは空白です。
階乗を再帰で求める
# 階乗: 5 の階乗は 5 かける 4 かける 3 かける 2 かける 1 です。
def factorial(n):
print("呼ばれた:", n)
if n <= 1:
return 1
return n * factorial(n - 1)
print("答え:", factorial(4))
# 4 を 6 に変えて、呼ばれる回数を見ましょう。
呼び出しはスタックに積まれる
関数を呼ぶと、その関数の値がコールスタックに積まれます。基底ケースで答えが返ると、1つずつ取り出されて、戻っていきます。
スタックには深さの上限があります。Python では、ふつう千回ほどの呼び出しで止まります。基底ケースがないと、必ずこの上限に当たります。
ラボの端末で再帰を動かす
端末の bash でも、関数は自分を呼べます。1つ目の Run は、階乗の関数を書いて 5 で呼びます。
2つ目と3つ目は、Python の計算で、同じ答えを確かめます。さきほどの表の最後の値と、見比べましょう。
bash で再帰の階乗
f() { if [ $1 -le 1 ]; then echo 1; else echo $(( $1 * $(f $(( $1 - 1 )) ) )); fi; }; f 5ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
Python の階乗で確かめる
python3 -c "import math; print(math.factorial(5))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
1 から 5 の合計
python3 -c "print(sum(range(1, 6)))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
再帰は、自分を呼べばうまく動く、と思いがちです。止まる基底ケースがないと、呼び出しが積み重なって、エラーで止まります。さらに、呼ぶたびに問題が小さくなっていることも、確かめましょう。
フィボナッチ数は2回自分を呼ぶ
フィボナッチ数は、前の2つの数を足した数です。0, 1, 1, 2, 3, 5, 8 と続きます。
式は、fib(n) が fib(n-1) と fib(n-2) の和です。自分を2回呼ぶので、呼び出しが木のように増えます。正確な呼び出し回数を、次の表に示します。
fib(n) を呼んだときの呼び出し回数
| n | 呼び出し回数 |
|---|---|
| 5 | 15 |
| 10 | 177 |
| 20 | 21891 |
| 30 | 2692537 |
学生が入力するセルは、このプレビューでは空白です。
フィボナッチの呼び出しを数える
# フィボナッチ数: 0, 1, 1, 2, 3, 5, 8 と続きます。呼ばれた回数を数えます。
calls = [0]
def fib(n):
calls[0] = calls[0] + 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(10), "呼ばれた回数:", calls[0])
# 10 を 15 に変えて、回数がどれだけ増えるかを見ましょう。
さらに挑戦: 文字を逆にする
課題が通ったら、文字列を逆にする再帰の関数を書きましょう。基底ケースは、空の文字列です。
再帰ケースは、先頭の1文字を最後に回し、残りを逆にしたものに付けます。"abc" で、呼び出しの順を表に書いてみましょう。