Pythonで再帰関数！
再帰関数ってなんだかわかりにくい。わかったつもりでも、やっぱり？がつくことが多い。
解説されているので自分でも実行してみる。
まずよくみるやつ"階乗"。
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)与えられた数を全て掛け合わせる。立とえば"3"を引数に入れると
3*2*1 = 6
と出る。
3を入れた場合はnは0ではないので
3 * factorial(2)となります。
factorial(2)と言うのは同じくnは0でないので
2 * factorial(1)factorial(1)と言うのは
1 * factorial(0)1 * factorial(0)となります。nが0となるのでこの結果は
1 * 1 = 1
となります。と言うことは遡って、2 * factorial(1)は
2 * 1 = 2
3 * factorial(2)は
3 * 2 = 6
となります。結果的に
3 * 2 * 1 = 6
となります。でもなんだかややこしいですね。
もっと簡単に
def countdown(n):
if n <= 0:
print("Liftoff!")
else:
print(n)
countdown(n-1)とすると3を入れると
3,2,1,Liftoff!
と出力されます。
仕組みは"3"を入れた場合はまず0以上なので
else:
print(n)
countdown(n-1)を実行することになり
print(n)でそのまま"3"が出力されます。
そして
countdown(n-1)再帰となるのでこの繰り返しが続いて
"0"になったら
if n <= 0:
print("Liftoff!")が実行され
"Liftoff!"が出力されます。
この再帰関数は単純なんで
countdown(n-1)
が繰り返されていることがわかりやすいと思います。
最初に紹介しているfactorialの場合はfactorial()の関数
n * factorial(n-1)
は関数の計算にnを掛けて計算を求めないといけないので実質、
n = 0
のところで数字が"1"のところでfactorial(n-1)の答えが出る。その数字を使って遡って計算、この場合"n"に掛けていくイメージです。
再帰関数のメリットとデメリット メリット: 問題をシンプルに解決できる。 コードが直感的で理解しやすい。 デメリット: 深い再帰はメモリを大量に消費する。 無限ループのリスクがある。
シンプルにはなりますがある程度理解しないと難しいく感じます。
代表的な関数です。
フィボナッチ数列
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
以下サイトで理解が進むと思います。