再帰関数とは
2分探索を再帰関数を使った方法で取り組む前に、再帰のおさらいをしておく。再帰関数とは、自分自身を呼び出す関数のことで、下記の条件をもつ関数のこと。
- 再帰関数の中で自分自身を呼び出す
- 終了条件を書く
- 終了条件に向かうように自分自身を呼び出す
文字で書かれてもよくわからいので、実際にコードを書いてみよう。
再帰的なカウントダウン
カウントダウンを行うプログラムを再帰的なカウントダウンとして実装してみる。カウントダウンなんか再帰で書く必要はない、という指摘はさておき。
def recursive_countdown(n):
if n == 0:
return print(0)
print(n)
return recursive_countdown(n - 1)
recursive_countdown(3)
3
2
1
0
この関数は下記の通り、再帰関数のための条件を持っている。
- 再帰関数の中で自分自身を呼び出す:
return recursive_countdown() - 終了条件を書く:
if n == 0: - 終了条件に向かうように自分自身を呼び出す:
return recursive_countdown(n - 1)
図解するとこのような感じで機能している。これをみるとわかるが、終了条件に向かわない場合や終了条件がない場合、無限に再帰関数を呼び出し続けることになる。
再帰関数サンプル
他にも文字を1文字づつ減らしていく関数も再帰で実行できる。
def prefixes(string):
if string == '':
return []
return [string] + prefixes(string[:-1])
print(prefixes('Apple'))
['Apple', 'Appl', 'App', 'Ap', 'A']
図解するとこのようなイメージ。
def fib(n):
if n <= 2:
return 1
return fib(n-2) + fib(n-1)
print(fib(6))
8
図解するとこのようなイメージ。
フィボナッチ数列のように再帰関数が2つある場合や、再帰がどんどん深くなるような場合、簡単であれば頭では処理できるけど、やっていることが複雑かつ再帰となると頭の処理がおっつかないので、デバッカーなり可視化してなんとかするしかないな…。
フラクタルツリー
再帰関数を使うことで、フラクタルツリーを描写できる。特定の条件まで、枝を分岐させていくことを繰り返すことで、木が描かれる。
import turtle
turtle.shape('turtle')
turtle.speed(0)
def tree(branchLen,t):
if branchLen > 5:
turtle.forward(branchLen)
turtle.right(20)
tree(branchLen-15,t)
turtle.left(40)
tree(branchLen-15,t)
turtle.right(20)
turtle.backward(branchLen)
def main():
turtle.left(90)
turtle.up()
turtle.backward(300)
turtle.down()
tree(150, turtle)
main()
turtle.done()
