面试题：C++ 递归函数终止条件在复杂数列中的应用

Question

定义一个复杂数列：a(n) = a(n - 1) + a(n - 2) + n （当n > 2时），a(1) = 1，a(2) = 2 。请用C++ 递归函数实现该数列第n项的计算，重点设计合理的递归终止条件。同时说明如何通过修改终止条件来适应数列定义的小范围调整（例如a(1)值的改变）。

Answer 1

#include <iostream>

// 递归函数计算数列第n项
int complexSequence(int n) {
    // 递归终止条件
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else {
        return complexSequence(n - 1) + complexSequence(n - 2) + n;
    }
}

int main() {
    int n;
    std::cout << "请输入n的值: ";
    std::cin >> n;
    std::cout << "数列第" << n << "项的值为: " << complexSequence(n) << std::endl;
    return 0;
}

关于终止条件调整

1. 改变 a(1) 值：如果 a(1) 的值改变，例如变为 a(1) = k，只需将递归终止条件中 if (n == 1) 的返回值改为 k 即可。代码修改如下：

int complexSequence(int n) {
    // 递归终止条件
    if (n == 1) {
        return k; // k为a(1)的新值
    } else if (n == 2) {
        return 2;
    } else {
        return complexSequence(n - 1) + complexSequence(n - 2) + n;
    }
}

2. 改变 a(2) 值：类似地，如果 a(2) 的值改变，例如变为 a(2) = m，则将 if (n == 2) 的返回值改为 m 即可。代码修改如下：

int complexSequence(int n) {
    // 递归终止条件
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return m; // m为a(2)的新值
    } else {
        return complexSequence(n - 1) + complexSequence(n - 2) + n;
    }
}

这样通过简单修改递归终止条件的返回值，就能适应数列定义在初始值上的小范围调整。