再帰関数の自分用メモ

背景

• 深さ優先探索を学ぶにあたって再帰関数のコードを書く必要があった。
• 再帰関数の考えたをノートに整理して少し掴む事ができたので、それをまとめておく。

考え方

重要なのは、再帰関数の処理には2つのパターンがあると言う事を理解し、それぞれ今回の問題ではどう言う状況が考えられるかを整理することから始める。

2つのパターンとは以下

1. 再帰を行うパターン
2. 例外のパターン

再帰関数の基本である階乗(n!)のアルゴリズムを例に考えていく。

• 階乗のアルゴリズムにおける再帰を行うパターン

これは以下の数式のように現在の値に、1を引いた階乗を掛けるパターンである。
この場合、入れ子のようにまた同じ関数が現れるので、再帰が生まれている。

k\times(k-1)!

• 階乗のアルゴリズムにおける例外のパターン

これは、k = 1となったときである。
この時には、ひとつ小さい値である0!(=1)を加える必要はなく、ここで処理を止める必要がある。

再帰関数ではどこかで処理を止めないと無限ループが起こるので、この例外のパターンというのはいわば、再帰関数を使わないパターンである。

整理した情報を元に実装を行う。

# 階乗を再帰関数で定義

def factorial(n):
  # 再帰のパターン
  if n > 1:
    return n * factorial(n-1)
  # 例外のパターン
  else:
    return 1

# 答えを確認
print(factorial(3))

今後再帰関数の実装で困ったときは、一度この二つのパターンに立ち返るようにする。