*今回は再帰(Recursion)の少し発展的なでも有名な内容です。
もし再帰(Recursion) ってなに?ってなっている方はこちらを先にお読みください.
今回のテーマはタイトル通りフィボナッチ数列をプログラミングで表現するというものです。明確にいうと、nの値を入力するとそのnの値のフィボナッっち数列を返す関数のコードを書くことです。
フィボナッチ数列って何?
フィボナッチ数列とは、AnがAn-1とAn-2の和になっている数列のことです。
1 1 2 3 5 8 13 21
などです。例えば8で考えると、その前の項とそのもう一つ前の項(8からみて2つ前)の項の和が3+5=8になっているのが確認できると思います。
もし数学的に考えるのであれば、一般項を求めなくてはですが、フィボナッチ数列は「AnがAn-1とAn-2の和になっている数列」と漸化式で説明できるので、それをそのまま関数としてコードに書いて行きたいと思います。
コードはこんな感じ!
今回のアルゴリズム
def fibonacii(n):
#base case = 再帰が終わる場所
if n == 1 or n == 2:
return 1
#Recursion = 再帰する部分
return fibonacii(n-1) + fibonacii(n-2)
print(fibonacii(6))
再帰の部分について
今回少し難易度が上がったのは再帰している部分が2つになったところだと思います。
ですが、基本は前回の記事と同じ理屈です。
今回n=6の時のフィボナッチ数列を求めるコードになっています。(関数部分はnが自然数であればいくらでもいいのですが、mainのコードでfibonaciiに6を入れているのでn=6が求まります。)
よって最初は return fibonacii(6-1) + fibonacii(6-2)で再帰されて、そこからnの値が1,2になるまで減っていきます。そして底(n=1,n=2)に到達したあと順々に fibonacii(n-1), fibonacii(n-2)の値が分かっていき関数が結果を返します。
ベースケースについて
今回ベースケースはn = 1とn = 2の二つになっています。
フィボナッチ数列AnをAn-1とAn-2の和という形で表現しているのですが、n=1,n=2にはそれより1つ、二つ前の値が存在しないためベースケースをn=1,n=2の2つを用意する必要があるのです。
どうでしたでしょうか?
もしコメント、リアクションなどいただけると喜んで拝見させていただきます。
ではまた別の記事で。