参考にした動画
https://youtu.be/vYquumk4nWw
英語の動画だけど、すごい聞き取りやすいし分かりやすいね
この動画の例ではフィボナッチ数列を使ってたから、フィボナッチ数列を求めるための再帰関数書いていくよー。
まずは簡単なやつ
practice.py
def fib(n):
if n == 1 or n == 2:
result = 1
else:
result = fib(n-1) + fib(n-2)
return result
例えばn=５の時はまず、n=3とn=4に分岐して、そこからn=3⇨(n=2,n=1)となっていって、n=4⇨((n=3⇨n=2,n=1),n=2)みたいにn=2かn=1まで分裂を繰り返していく、分裂が完全に完了したら分裂の数分、数が足されていって、最終的にn=5の値5が戻り値として戻ってくる。
しかし、毎回毎回一からやっていったら計算量がバカにならないので、初めてでた数字はリストに追加していくようにするともっと良くできる。
practice.py
def fib(n, memo):
if memo[n] != None:
return memo[n]
if n == 1 or n == 2:
result = 1
else:
result = fib(n-1) + fib(n-2)
memo[n] = result
return result
今回は作らないけれど、本番では問題や状況にあったmemoリストを作ります。そして最初に既にその数字が求められていたのなら、その数字を返します。もし初めての数字ならば一個前のコードと同じ処理をしてnの数字を求め出してリストに格納していきます。上の動画によると計算量がO(2**n)からO(n)まで減るらしいので、memoを用意しておく効果は絶大です！