php - 自分自身を呼び出すphp関数

Question

なぜ答えは、与えられた13です。頭が回らないだけです。

指定された入力が7の場合、次の関数は何を返しますか。

function foo($bar) {
  if ($bar == 1) return 1;
  elseif ($bar == 0) return 0;
  else return foo($bar - 1) + foo($bar - 2);
}

正解：D。13

Answer 1

nneonneo は答えとして彼のコメントを投稿したはずですが、再帰の概念は次のように機能します。

フー(7) = フー(6) + フー(5)

しかし、待ってください、それらは何に等しいのですか?

フー(6) = フー(5) + フー(4)

おやおや！

フー(5) = フー(4) + フー(3)

うーん..パターンが浮かび上がる..

フー(4) = フー(3) + フー(2)

フー(3) = フー(2) + フー(1)

フー(2) = フー(1) + フー(0)

フー(1) = 1

と

フー(0) = 0.

これで、値に逆戻りして理解できるようになりましたが (これはより重要な質問です)、$bar を 1 ずつ増やすと、実際には何が起こっているのでしょうか?

foo(8) は foo(7) と比べてどうですか?

そして答えは、foo (8) は foo(7) + foo(6) に等しいということです。言い換えれば、それは 13 + 8 に等しい - foo の前の 2 つの出力の合計 .. ちょっと、おなじみですね ... 前の 2 つの数値の合計に等しい有名なシーケンスはありますか?

1、2、3、5、8、13 ...

そうです、これがフィボナッチ数列を再帰的に計算する方法です。そして、フィボナッチ数列をどのように構築するかを考えると、それは本当に

1、1 + 1、2 + 1、3 + 2、5 + 3、8 +5

どちらがちょうど

1、1 + 1、(1 + 1) + 1、(2 + 1) + (1 + 1) など

初期値 (位置 "0" は 0、位置 1 は 1) を "シード" し、それらを合計すると、元のシードと多くの加算だけを使用してシーケンス内の各数値を導出できます。

したがって、この場合、バーはフィボナッチ数列でのバーの位置を表します。したがって、数列の 7 番目の数は 13 です。

Answer 2

非常にシンプルで、シーケンスを手作業でトレースするだけです。このタイプの再帰を使用する場合、プログラミング手順というよりも数学関数として考えると役立ちます。より自然にそれを知りたいのであれば、関数型言語* MLまたはいくつかのLISPで遊ぶことは、あなたを大いにそして非常に迅速に助けるでしょう。データ構造（スタック/キュー）に再帰がある場合、それは少し異なりますが、関数型プログラミングの経験もそれを助けます。

foo(0)= 0

foo(1)= 1

foo(2)= foo(1)+ foo(0)= 1 + 0 = 1

foo(3)= foo(2)+ foo(1)= 1 + 1 = 2

foo(4)= 2 + 1 = 3

foo(5)= 3 + 2 = 5

foo(6)= 5 + 3 = 8

foo(7)= 8 + 5 = 13