关于C++算法的问题

 __int64 fib ( int n, __int64& prev ) { //计算Fibonacci数列第n项（线性递归版）：入口形式fib(n, prev)
    if ( 0 == n ) //若到达递归基，则
      { prev = 1; return 0; } //直接取值：fib(-1) = 1, fib(0) = 0
    else { //否则
      __int64 prevPrev; prev = fib ( n - 1, prevPrev ); //递归计算前两项
      return prevPrev + prev; //其和即为正解
   }
 } //用辅助变量记录前一项，返回数列的当前项，O(n)

这段代码如果n大于等于2，计算else时prevPrev不是与prev绑定了吗，最后递归回代时返回0，prev和prevPrev都是0了，那不就算不出来了吗？

prevPrev不是与prev绑定了吗
不是，下一层的prev是上一层的 prevPrev 的引用
而本层的prev则是上层的prevPrev ，是不同的变量。

【以下回答由 GPT 生成】

问题分析: 在这段代码中，的确存在一个问题。当n大于等于2时，在递归调用的过程中，prevPrev并没有正确地与prev绑定，导致返回的prevPrev的值不正确。因此，代码无法正确计算斐波那契数列的第n项。

解决方案: 为了解决这个问题，我们需要对代码进行一些修改。具体的解决方案如下:

__int64 fib ( int n ) { // 新的斐波那契数列计算函数
  if ( 0 == n ) { // 若到达递归基，则
    return 0; // 返回fib(0) = 0
  }
  else if ( 1 == n ) { // 另外处理fib(1) = 1的情况
    return 1; // 返回fib(1) = 1
  }
  else { // 递归计算
    __int64 prevPrev = 0; // 初始化前两项的值
    __int64 prev = 1;
    for (int i = 2; i <= n; i++) { // 循环计算直到第n项
      __int64 temp = prevPrev + prev; // 计算下一项的值
      prevPrev = prev; // 更新前两项的值
      prev = temp;
    }
    return prev; // 返回第n项的值
   }
} // 不再需要辅助变量，直接返回数列的当前项，O(n)

在这个修改后的代码中，我们没有使用递归来计算斐波那契数列，而是使用循环。我们通过初始化prevPrev和prev为斐波那契数列的前两项，并在循环中根据前两项的值计算下一项的值。最后，我们返回第n项的值。

这样修改后的代码可以正确地计算斐波那契数列的第n项，并且不再有之前的问题。

希望这个解决方案对您有所帮助。如果您有任何疑问，请随时提问。

【相关推荐】

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7767097