2

我在一次采访中得到了这个问题。所以，在我看来，这似乎是一个混乱的斐波那契序列。和生成器，这给出了一个stackoverflow。因为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)。如您所见，一旦达到 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

忽略不正确的终止条件，代码是斐波那契函数的“天真”递归实现。它的大 O 时间复杂度非常差。它适用于小 n，但如果 n 大于 50（我只是在猜测这个数字），那么它将需要“永远”才能运行。

于 2010-09-08T09:40:44.793 回答