0

再帰に基づくいくつかの操作を示す以下のコードを見つけてください。この再帰がどのように機能するかを説明してください。

#include <stdio.h>
int func(int);
main()
{
  int ret = 0;
  ret = func(6);
   printf("The val is %d\n",ret);

}

int func(int m)
{
    if((m==0)||(m==1))
    {
       return 1;
    }
    else
    {
      return (func(m-1)+func(m-2));
    }
}

実行すると、val の値は 13 になります。このアンワインド操作がスタックでどのように発生するのか、誰か説明してください。

4

3 に答える 3

6

スタックや巻き戻しを行う必要はありません (ただし、自分自身を巻き込んで申し訳ありません)。

呼び出しを関数の内容に置き換えるだけで、再帰がなくなるまでそれを続けます。

ret = func(6) =
      func(5) + func(4) =
      func(4) + func(3) + func(3) + func(2) =
      func(2) + func(3) + func(1) + func(2) + func(1) + func(2) + func(0) + func(1) =
      func(0) + func(1) + func(1) + func(2) + 1 + func(0) + func(1) + 1 + func(1) + func(0) + 1 + 1 =
      1 + 1 + 1 + func(0) + func(1) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 =
      3 + 1 + 1 + 8 = 
      3 + 2 + 8 =
      13

タイポグラフィーで少し難しいですが、それが起こり、答えもあなたが得たものと一致するようです.

于 2013-01-29T09:30:04.250 に答える
3

再帰は、その特定の関数内から関数を呼び出すことに他なりません。多くの数学的アルゴリズムまたは (ツリー) 検索アルゴリズムは、この手法を使用して目的の結果を得ています。

再帰的な関数呼び出しは、繰り返される「自己呼び出し」を「エスケープ」する必要があります。そうしないと、アプリケーションが応答しなくなります。あなたの例では、これはif((m==0)||(m==1))チェックによって行われます。チェックが真の場合、関数は 1 を返します (そして再帰をエスケープします)。

あなたが示した再帰コードは、2つの前の計算の値を必要とするため、典型的な再帰アルゴリズムであるフィボナッチ数列を計算します。ステップ 0 と 1 は に戻り1ます。これら 2 つの値は、ステップ 2 で加算されます (結果は になり1+1=2ます)。次のステップの結果は1+2=3. 等々。ご覧のとおり、これは最初からしか計算できません (したがって、そうするには再帰が必要です)。

于 2013-01-29T09:30:31.913 に答える
2

プログラムは、フィボナッチ数列のn番目（またはn + 1番目）の数を出力しようとします。ここでの基本的なケースはm =1 or m=0

ここでの再帰の最悪のことは、値が2回計算されることです。たとえば、ここから明らかなように、func（4）、func（3）、func（2）です。ここに画像の説明を入力してください

于 2013-01-29T09:43:41.483 に答える