我在一次采访中得到了这个问题。所以,在我看来,这似乎是一个混乱的斐波那契序列。和生成器,这给出了一个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 行代码时,你会推断出什么。没有调试。
是的,它只是一个带有不正确基本情况的递归斐波那契方法(尽管我认为我不会使用n < 3
任何一种......这取决于你如何定义它)。
至于“预期的答案是什么” - 这取决于问题。您是否在帖子标题中准确地问过这个问题?如果是这样,答案是“它会永远递归,直到当你传递除 0 以外的任何值时它会炸毁堆栈”——当然还有解释。(它永远不会结束,因为n-1 不是 0,或n-2 不是 0,或两者兼而有之。)
编辑:以上回答了第一个问题。要回答“当你看到这 3 行代码时你会推断什么”——我会推断有问题的开发人员从未运行过除 0 以外的值的代码,或者不关心代码是否有效。
发布代码的问题是,如果我们评估 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);
}
}
假设,您调用 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);
}
它是第 0 个元素为 1 的递归斐波那契函数。
忽略不正确的终止条件,代码是斐波那契函数的“天真”递归实现。它的大 O 时间复杂度非常差。它适用于小 n,但如果 n 大于 50(我只是在猜测这个数字),那么它将需要“永远”才能运行。