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

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);
}

这个函数是正确的尾递归函数。

尾递归函数是所有路径结束的函数（即 return）一个值（-1 表示负数，prev2 表示 1 和 0）或调用函数（它不需要直接是它自己；尽管如果它不直接或间接地调用自己，它就不会是尾递归的）。

Fibonacci 不是展示尾递归的好例子，因为它混淆了尾递归（相当于迭代循环）和避免冗余调用的优化（原始 fibonacci函数在最后一个例子中调用了自己两次）。

考虑 factorial 函数：

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

当您调用 factorial(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;
    }
}

如果编译器足够聪明，尾递归函数的代码会转换为该函数生成的等效代码。

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

tail recursive version of the fibonacci function

c

recursion

tail-recursion