C语言写斐波拉契数列尾递归
时间: 2024-09-08 09:04:57 浏览: 77
尾递归优化:C语言中的性能艺术
斐波那契数列是一个经典的数学问题,通常通过动态规划或迭代方法来解决。然而,对于尾递归优化的语言(如Scheme、Racket等),我们可以利用其特性编写一个尾递归版本的斐波那契函数。在C语言中,虽然不是原生支持尾递归优化,但我们仍然可以尝试设计一种形式来模拟,避免栈溢出的问题。
下面是一个非标准的尾递归版本,它使用了一个临时变量`prev`来保存前两个数字:
```c
#include <stdio.h>
// 使用循环而非递归实现尾递归
long long fibonacci_tail_rec(long long prev, long long curr, int n) {
if (n == 0)
return prev;
else if (n == 1)
return curr;
else
return fibonacci_tail_rec(curr, prev + curr, n - 1);
}
// 转换为常规调用
long long fibonacci(int n) {
if (n <= 0)
return 0;
long long first = 0, second = 1;
return fibonacci_tail_rec(first, second, n);
}
int main() {
int n = 10; // 想要计算的斐波那契数的位置
long long fib = fibonacci(n);
printf("Fibonacci of %d is %lld\n", n, fib);
阅读全文