最近出会した再帰問題について，ざっくりとしたアイデアを備忘録として残しておく．
言語はPythonを使用する．
再帰とは
再帰とは，手続や関数が「自分自身を呼び出すこと」．
関数の定義の中に，関数自身が登場する．
まず条件判定を行い，下記のいずれかを行う．
- 再帰呼び出しは行わず，特定の処理を行う
- 関数自身を呼び出す
再帰アルゴリズムの例
- 階乗計算
-
階乗とは「ある正の整数（N）から1までの整数の積」のこと.
（例）5! = 5 x 4 x 3 x 2 x 1
「n個の異なるものを1列に並べる場合の並べ方」を計算する場合に用いられる．
実際に解いてみる
階乗計算を，再起呼出しを使って解くとはどういうことか．
先程挙げた例題を再帰の考え方で解くと．
5! = 5 x 4!
ここで 4! = 4 x 3! であり，同様に続けて， 3! = 3 x 2!，2! = 2 x 1!，
そして最後に 1! = 1 とし，これ以上再帰は行わず，2!から5!までの答えが順に出る．
そしてこれらは次の関数f(x)で表すことが出来る．
f(x) =
\begin{cases}
N > 0 のとき & N x f(N-1) \\
N = 0 のとき & 1
\end{cases}
コードで表すと下記のような感じ．
自身の関数を呼び出すことで，繰り返し計算を行なっている．
recursive.py
def kaijyo(n):
if n == 1:
return 1
else:
return n * kaijyo(n - 1)
print('Answer:', kaijyo(5))
結果は下記の通り．
output.py
Answer: 120
再帰を使う利点
再帰呼び出しの考え方を知っていると何が良いかというと，プログラムをシンプルに記述することが出来る．
ちなみに先程の階乗計算を，再帰呼び出しを使わずループを用いて記述すると，次のようになる．
non-recursive.py
n = 5
answer = 1
for i in range(n, 1, -1):
answer *= i
print('Answer:', answer)
結果は下記の通り．
output.py
Answer: 120
考察
何でもかんでもforループで力技で片付けようとするとコードが長くなってしまうことがあるが，
再帰を使うと，実際かなり面倒な問題もシンプルに解けそうだ．
代表的なものにクイックソートやハノイの塔などがあるそうで，次回はそれらの問題にも挑戦したい．