c - 处理 sqrt (2) 的连续分数表示的分子的序列的递归函数

Question

我试图开发一个递归函数来找到序列的第 n 项（1,1,3,7,17​​,41,99,239,577,1393 ...），但是，我没有成功：

int progRec(int n){
        return 2*progRec(n-1) + progRec(n-2);}

有什么想法吗？

标签： cfunctionrecursion

Answer 1

添加停止条件。我假设它是1 if n <= 2：

int progRec(int n) {
    if (n <= 2) {
        return 1;
    }
    return 2 * progRec(n - 1) + progRec(n - 2);
}

您可以通过消除第二个分支来优化此递归，这只是重新计算已访问的值。只需将先前计算的项作为参数传递：

int progRec(int n, int val = 1, int prev = 1) {
    return n <= 2 ? val : progRec(n - 1, 2 * val + prev, val);
}

您可以将其进一步优化为for循环，因为现在它只是一个尾递归函数。