递归实现斐波那契数列指定索引值返回问题求助

核心问题分析 #

你的代码存在几个关键问题，直接导致返回结果错误和"invalid pointer"异常：

1. 递归分支未返回值
   在else分支的递归调用处，你执行了fibonacci(index, counter, FibVal, FibList);但没有返回这个调用的结果。函数走到这个分支时没有return语句，会触发未定义行为——可能返回垃圾内存值，甚至引发指针错误。

2. vector按值传递导致的无效操作
   你把vector<BigNumber>按值传入函数，每次递归都会创建一个全新的副本。递归中对FibList的修改只作用于副本，上层调用的vector根本不会更新，最终导致访问越界或者返回错误值。必须改用引用传递（vector<BigNumber>& FibList），让所有递归操作共享同一个vector。

3. 斐波那契计算逻辑错误
   原代码中FibVal += FibList[index - 1];不符合斐波那契数列的定义，正确的计算应该是当前数等于前两个数之和：FibVal = FibList[index] + FibList[index - 1];。

4. 返回类型不匹配（潜在问题）
   函数声明返回fibonacciType1，但你实际返回的是BigNumber类型的FibList[index]。如果fibonacciType1不是BigNumber的别名，这种类型不匹配会直接导致内存错误，比如将对象转换成指针类型时出现"invalid pointer"。

修正后的代码 #

// 假设fibonacciType1是BigNumber的别名，若不是请统一返回类型
BigNumber fibonacci(int index, int counter, BigNumber FibVal, vector<BigNumber>& FibList) {
    // 基准条件：到达目标索引时返回对应值
    if (index == counter) {
        return FibList[index];
    }
    // 处理counter为0的边界情况
    if (counter == 0) {
        return FibList[0];
    }
    // 正确计算下一个斐波那契数
    FibVal = FibList[index] + FibList[index - 1];
    FibList.push_back(FibVal);
    // 必须返回递归调用的结果
    return fibonacci(index + 1, counter, FibVal, FibList);
}

int main() {
    cout << "Do not change this line.  Enter a sequence of increasing Fibonacci indicies and -1 to stop input." << endl;

    int counter{0};
    while (cin >> counter, -1 != counter) {
        vector<BigNumber> FibList{0, 1};
        // 直接处理小索引，避免不必要的递归
        if (counter == 0) {
            cout << counter << endl << FibList[0] << endl;
        } else if (counter == 1) {
            cout << counter << endl << FibList[1] << endl;
        } else if (counter < 0) {
            cout << counter << endl << "Invalid index" << endl;
        } else {
            BigNumber FibVal{1};
            cout << counter << endl << fibonacci(1, counter, FibVal, FibList) << endl;
        }
    }
    return 0;
}

额外注意事项 #

• 确保BigNumber类正确重载了operator+（用于斐波那契数的加法）和operator<<（用于输出），否则加法和打印操作会失败。
• 引用传递vector不仅解决了数据同步问题，还大幅提升了递归效率，避免了大量不必要的内存拷贝。

内容的提问来源于stack exchange，提问作者AskingLotsOfQuestions