2

私はインタビューでこの質問を受けました。だから、これは私にはめちゃくちゃなフィボナッチ数列のようです。合計ジェネレーターとこれはスタックオーバーフローを与えます。なぜならif(n==0) should be if(n<3)（出口条件が間違っている）。この質問に対する正確な答えは何でしょうか？答えとして何が期待されましたか？

foo (int n) {
if (n == 0) return 1;
return foo(n-1) + foo(n-2);
}

アップデート

この再帰関数は何をしますか？

これらの3行のコードを見ると、何を推測しますか。デバッグなし。

4

5 に答える 5

5

はい、これはベースケースが正しくない再帰的なフィボナッチ法です（私も使用しないと思いますn < 3が...定義方法によって異なります）。

「答えとして何が期待されたのか」については、質問によって異なります。投稿のタイトルにある質問を正確に聞いたのですか？もしそうなら、答えは「0以外の値を渡したときにスタックを爆破するまで永遠に繰り返されます-もちろん説明付きです。（n-1が0でないか、 n-2が0でないか、またはその両方であるため、終了することはありません。）

編集：上記は最初の質問に答えます。「これらの3行のコードを見たときに何を推測しますか」と答えるには、問題の開発者が0以外の値でコードを実行したことがないか、コードが機能するかどうかを気にしないと推測します。

于 2010-09-08T08:49:12.170 に答える
2

投稿されたコードの問題は、foo（1）を評価する場合、foo（0）とfoo（-1）を見つける必要があり、foo（-1）はfoo（-2）とfoo（-3）を見つける必要があるということです。等々。これにより、メモリにスペースがなくなるまでfoo（）への呼び出しが増え続け、スタックオーバーフローが発生します。fooに対して行われる呼び出しの数は、実装固有の呼び出しスタックのサイズによって異なります。

これらのコード行を見ると、それを書いた人は誰でも、関数に供給できる可能性のあるすべての入力について考えていなかったという印象を受けます。

foo（1）または負の入力で失敗しない再帰的なフィボナッチ関数を作成するには、次のようにします。

foo (int n) {
  if( n < 0 ) return 0;
  if (n == 0) return 1;
  return foo(n-1) + foo(n-2);
}

編集：フィボナッチ数列は負のインデックスに対して暗黙的に定義されていないため、おそらく負の数の戻り値は別のものになるはずです。

ただし、fib（-n）=（-1）^（n + 1）fib（n）という拡張機能を使用すると、次のコードを取得できます。

int fib(int n) {
     if( n == -1){
        return 1;
     }else if ( n < 0 ){ 
        return ( (-1)^(-n+1 ) * fib(-n) );
     }else if (n == 0){
        return 1;
     }else{
        return fib(n-1) + fib(n-2);
     }
}
于 2010-09-08T08:49:22.047 に答える
0

foo（1）を呼び出すと、foo（0）とfoo（-1）の2つのサブ呼び出しがあります。ご覧のとおり、foo（-1）に到達すると、nは無期限に減少し、終了条件に達することはありません。

正確な答えは次のとおりです。

foo (int n) {
 if (n <= 1) return 1; // assuming 0th and 1st fib is 1
 return foo(n-1) + foo(n-2);
}
于 2010-09-08T08:51:49.717 に答える
0

その再帰的フィボナッチ関数は、0番目の要素が1です。

于 2010-09-08T09:36:50.857 に答える
0

誤った終了条件を無視すると、コードはフィボナッチ関数の「ナイーブ」な再帰的実装になります。それは非常に貧弱なbig-O時間計算量を持っています。nが小さい場合は問題なく動作しますが、nがたとえば50より大きい場合（私はその数を推測しているだけです）、実行には「永遠に」かかります。

于 2010-09-08T09:40:44.793 に答える