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 回答