反復
反復はプロセスの繰り返しです。学校に通う生徒は、卒業するまで毎日学校に通うプロセスを繰り返します。少なくとも月に1、2回は食料品店に行って商品を購入しています。このプロセスを毎月繰り返します。数学では、フィボナッチ数列はタスクの繰り返しの特性にも従います。最初の2つの数が0と1であるフィボナッチ数列を考えてみましょう。他のすべての数は前の2つの数の合計です。
0、1、1、2、3、5、8、13、21、34、55、89
反復手順
フィボナッチの公式は次のように書くことができます。
F（n）= F（n – 1）+ F（n – 2）
フィボナッチ（0）= 0
フィボナッチ（1）= 1
フィボナッチ（2）=フィボナッチ（1）+フィボナッチ（0）= 1 + 0 = 1
フィボナッチ（3）=フィボナッチ（2）+フィボナッチ（1）= 1 + 1 = 2
フィボナッチ（4）=フィボナッチ（3）+フィボナッチ（2）= 2 + 1 = 3
フィボナッチ（5）=フィボナッチ（4）+フィボナッチ（3）= 3 + 2 = 5
フィボナッチ（6）=フィボナッチ（5）+フィボナッチ（4）= 5 + 3 = 8
以下に示すアルゴリズムは、n番目のフィボナッチ数を返します。
再帰
新しいフィボナッチ数（n番目の数）を取得するたびに、次のn番目のフィボナッチとして（n + 1）番目のフィボナッチを見つけると、そのn番目の数は実際には（n – 1）番目の数になります。上記の反復ステップを見ると、n = 2の場合、
フィボナッチ（2）=フィボナッチ（2-1）+フィボナッチ（2-2）=フィボナッチ（1）+フィボナッチ（0）= 1 + 0 = 1
ここで、フィボナッチ（3）、つまりn = 3を生成します。
フィボナッチ（3）=フィボナッチ（3-1）+フィボナッチ（3-2）=フィボナッチ（2）+フィボナッチ（1）= 1 + 1 = 2
つまり、nが増加するたびに、現在の（n – 1）番目と（n – 2）番目のフィボナッチの値も増加します。しかし、各nの（n – 1）番目と（n – 2）番目のフィボナッチを追跡するのは面倒です。自分自身を呼び出して反復のタスクを自分で繰り返すメソッドを作成するのはどうですか？
自分自身を呼び出すメソッドは、再帰メソッドと呼ばれます。再帰メソッドには、プログラムがそれ自体の呼び出しを停止する基本ケースが必要です。フィボナッチ数列の基本ケースは、fibonacci（0）= 0およびfibonacci（1）= 1です。それ以外の場合、Fibonacciメソッドはそれ自体を2回呼び出します– fibonacci（n – 1）およびfibonacci（n – 2）。次に、それらを追加してフィボナッチ（n）を取得します。 n番目のフィボナッチを見つけるための再帰的な方法は次のように書くことができます–
注意深く見ると、再帰はスタックの特性に従います。小さなサブ問題を解決して、問題の解決策を取得します。 n> 1の場合、最後の行を実行します。したがって、n = 6の場合、関数はfibonacci（6 – 1）とfibonacci（6 – 2）を呼び出して追加します。 fibonacci（6 – 1）またはfibonacci（5）は、fibonacci（5 – 1）およびfibonacci（5 – 2）を呼び出して追加します。この再帰は、6がベースケース値であるfibonacci（0）= 0またはfibonacci（1）= 1に達するまで続きます。ベースケースに到達すると、2つの基本値が追加され、fibonacci（の値を取得するまで上昇します。 6）。以下は、再帰のツリー表現です。
再帰ツリー
ご覧のとおり、再帰はどれほど強力である可能性があります。上記のツリーを作成しているのは1行のコードだけです（ベースケースを含む上記のコードの最後の行）。再帰はスタックを維持し、ベースケースに到達するまでさらに深くなります。動的計画法（DP）：再帰は理解とコーディングが簡単ですが、時間とメモリの点でコストがかかる可能性があります。以下の再帰ツリーを見てください。 fib（4）で始まる左側のサブツリーとfib（4）で始まる右側のサブツリーはまったく同じです。それらは3である同じ結果を生成しますが、同じタスクを2回実行しています。 nが大きな数（例：500000）の場合、同じサブタスクを複数回呼び出すため、再帰によってプログラムが非常に遅くなる可能性があります。
再帰ツリー-丸で囲まれています
この問題を回避するために、動的計画法を使用できます。動的計画法では、以前に解決したサブタスクを使用して、同じタイプの将来のタスクを解決できます。これは、元の問題を解決するためのタスクを減らす方法です。以前に解決したサブタスクソリューションを格納する配列fib []を作成しましょう。 fib [0] = 0およびfib [1] = 1であることはすでにわかっています。これら2つの値を格納しましょう。さて、fib [2]の値は何ですか？ fib [0] = 0およびfib [1] = 1はすでに保存されているので、fib [2] = fib [1] + fib [0]と言うだけです。同様に、fib [3]、fib [4]、fib [5]、……、fib [n]を生成できます。以前に解決されたサブタスクは、元のタスクが解決されなくなるまで次のサブタスクを取得するために呼び出されるため、冗長な計算が削減されます。
