斐波那契函数的尾递归版本

Question

我很难理解尾递归的概念，我想做一个斐波那契函数的尾递归版本，到目前为止，这是我想出的，但我不知道它是否正确，有人能帮我吗，任何帮助都将不胜感激

#include <stdio.h>

int fibonacci(int n)
{
    if(n==1)return 1;
    if(n==2)return 1;
    return fibonacci(n-1)+fibonacci(n-2);
}


int fibonacci_tail_Recusive(int n,int prev1,int prev2)
{
    
    if(n<0) return -1;
    if(n==1||n==0) return prev2;
    return fibonacci_tail_Recusive(n-1,prev2+prev1,prev1);
}

int fibonacci_tail_Recusive_wrapper(int n)
{
    return fibonacci_tail_Recusive(n,1,1);
}


int main()
{
    printf("tail recursive result: %d  normal recursive result:%d", fibonacci_tail_Recusive_wrapper(23) ,fibonacci(23));

    return 0;
}

代码编译并输出正确的结果

Answer 1

int fibonacci_tail_Recusive(int n,int prev1,int prev2)
{
    
    if(n<0) return -1;
    if(n==1||n==0) return prev2;
    return fibonacci_tail_Recusive(n-1,prev2+prev1,prev1);
}

正确地说，这个函数是尾部递归的。

尾部递归函数是指所有路径结束（即，返回）的函数，要么是一个值（-1表示负，prev2表示1和0），要么是对函数的调用（它不需要直接自身；但如果它不直接或间接调用自身，则不会是尾部递归）。

斐波那契并不是展示尾递归的好例子，因为这里它混淆了尾递归的好处（相当于迭代循环）和避免冗余调用的优化（原始fibonacci函数在最后一种情况下调用自己两次）。

考虑阶乘函数：

int factorial(int n)
{
    if (n == 0 || n == 1) return 1;
    return factorial(n - 1) * n;
}

调用阶乘（5）时，调用堆栈如下所示：

factorial(5)
   5 * factorial(4)
   5 * (4 * factorial(3))
   5 * (4 * (3 * factorial(2)))
   5 * (4 * (3 * (2 * factorial(1))))
   5 * (4 * (3 * (2 * 1)))
   5 * (4 * (3 * 2))
   5 * (4 * 6)
   5 * 24
   120

在每一步，乘法都在等待下一个操作数，以便计算其结果，这意味着每一步都需要保留一定量的内存。

使用尾部递归函数，如下所示：

int factorial(int n, int acc)
{
    if (n == 0 || n == 1) return acc;
    return factorial(n - 1, acc * n);
}

调用堆栈如下所示：

factorial(5, 1);
factorial(4, 5);
factorial(3, 20);
factorial(2, 60);
factorial(1, 120);
120

由于在每个步骤中，函数都完成了需要执行的所有计算，因此不需要为结果保留任何内存；每个调用覆盖当前帧；换句话说，它可以重写为一个循环：

int factorial(int n, int acc)
{
    while (true) {
        if (n == 0 || n == 1) return acc;
        acc = acc * n;
        n = n - 1;
    }
}

如果编译器足够智能，则尾部递归函数的代码将转换为该函数将生成的等效代码。