関数の再帰呼び出し
関数の再帰呼び出しとは、「関数 A の中から、この関数 A 自身を呼び出すこと」である。
「ある手続きを実行している最中に、同じ手続きを、違う対象について行う」といった入れ子構造になった処理。大きな問題が小さな問題に収束するように使う。
再帰のルール
- 再帰終了条件を持つ
- 状態を変更しながら再帰終了条件に進む
- 再帰的に関数自身を呼び出す
再帰関数の定義
再帰関数の定義は 2 つある。
- 終了条件。終了条件は、最小の問題を処理する箇所。再帰呼び出しをせずに直接的に値を返す。
- 再帰条件。再帰条件は「より小さな問題」を処理するための再帰呼び出しを行う。
問題を小さく分解していけば最終的に最小の問題を経由し終了条件が満たされるので、再帰が終了する。
関数の再帰呼び出しの例
次は再帰処理のシンプルな例である。引数 n を減算した値を、関数 total で加算しながらループさせ、n が 0 までたどり着いたときに再帰を停止する。
def total(n):
if n < 1: # 0 の時、再帰を停止
return 0
return n + total(n - 1) # 引数を減らしていく
print(total(3))
# 6
# 3 + 2 + 1
## 階乗の計算の例
次は階乗の計算（何通りの組み合わせがあるか？）を計算する例。引数に渡された数値を -1 しながら乗算している。
python
def fac(n):
if n == 1:
return 1
else:
return n * fac(n - 1)
print(fac(3))
# 6
# 3 * 2 * 1 = 6
リストのリストなど入れ子になったデータを平坦化するコード
def flat(x):
for i in x:
if isinstance(i, list):
for i_in in flat(i):
yield i_in
else:
yield i
x = [1, 2, [3, 4, 5], [6, [7, 8, 9]]]
list(flat(x))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]