这个递归函数有什么作用呢？

Question

我在一次采访中得到了这个问题。所以，在我看来，这似乎是一个混乱的斐波那契数列。求和生成器，这给出了一个堆栈溢出。因为 if(n==0) 应该是 if(n<3) （退出条件错误）。这个问题的准确答案应该是什么？预期的答案是什么？

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

更新

这个递归函数有什么作用？

看到这3行代码你会想到什么？无需调试。

Answer 1

是的，这只是一个递归斐波那契方法，其基本情况不正确（尽管我认为我也不会使用n <3...这取决于您如何定义它）。

至于“预期的答案是什么”——这取决于问题。您是否被问到了帖子标题中的问题？完全吗？如果是这样，答案是“它会永远递归，直到当你向它传递除 0 以外的任何值时它会炸毁堆栈”——当然还有解释。 （它永远不会结束，因为要么 n-1 不为 0，或 n-2 不为 0，或两者都不是。）

编辑：上面回答了第一个问题。要回答“当你看到这 3 行代码时你会推断出什么”——我会推断相关开发人员从未运行过 0 以外的值的代码，或者不关心代码是否有效。

Answer 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);
     }
}

Answer 3

假设，您调用 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);
}

Answer 4

它是一个递归斐波那契函数，第 0 个元素为 1。

Answer 5

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