斐波那契函数的尾递归版本
tail recursive version of the fibonacci function
我无法理解尾递归的概念,
我想制作斐波那契函数的尾递归版本,到目前为止,这就是我想出的
有但我不知道它是否正确,有人可以帮助我吗,任何帮助将不胜感激
#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;
}
代码编译并输出正确的结果
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;
}
}
如果编译器足够聪明,尾递归函数的代码会转换为该函数生成的等效代码。
我无法理解尾递归的概念, 我想制作斐波那契函数的尾递归版本,到目前为止,这就是我想出的 有但我不知道它是否正确,有人可以帮助我吗,任何帮助将不胜感激
#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;
}
代码编译并输出正确的结果
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;
}
}
如果编译器足够聪明,尾递归函数的代码会转换为该函数生成的等效代码。