在本例中，如何仅打印一次序列？(递归函数)
在本例中，如何仅打印一次序列？(递归函数)
提问于 2018-05-30 08:01:39
这只是一个斐波那契算法，我如何打印每个斐波纳契数列而不重复每一步？
递归函数在任何方面都是一个很好的用途吗？我知道它更易读，但是如果我把n= 40，在这个简单的算法中有一个明显的延迟，而迭代的方式是瞬时的。
int fib(int n)
{
if (n == 0)
{
return 0;
}
else if (n == 1)
{
return 1;
}
return fib(n - 1) + fib(n - 2);
}回答 2
Stack Overflow用户
回答已采纳
发布于 2018-05-30 12:08:15
像C这样的命令式语言并不总是很好地映射到算法的函数定义。
非递归通常更快，因为编译器和处理器都可以更容易地优化/并行执行，并且您不会浪费精力，不会不必要地推送和弹出堆栈。无论哪种方式，您只需要前两个fib值来计算下一个值：
void PrintNFibs(unsigned n)
{
size_t a = 1;
size_t b = 1;
size_t sum;
printf("0\n1\n1\n");
while ( n-- )
{
sum = a + b;
printf("%zu\n", sum);
a = b;
b = sum;
}
}根据算法本身定义算法(递归)是一回事，用C高效地实现算法是另一回事。然而，对于像斐波那契这样简单的东西，我不会使用递归，但不管怎样，这里有一个：
void PrintNFibsR(unsigned n)
{
static size_t a = 0;
static size_t b = 1;
static size_t sum;
sum = a + b;
if ( a == 0 )
{
printf("0\n1\n");
}
printf("%zu\n", sum);
if ( n > 1 )
{
a = b;
b = sum;
PrintNFibsR(n - 1);
}
}请注意，我们在这里真正做的就是传递循环计数器。浪费，但在技术上递归，如果不是真正的功能。编写看起来像递归Fibonacci算法定义的C代码的问题是，它毫无理由地消耗能量和堆栈空间。要以正确的顺序打印值，而无需事先计算和存储每个值，唯一的方法就是更改算法。
Stack Overflow用户
发布于 2018-05-30 08:48:45
您可以通过记忆已计算的值来轻松优化递归解决方案：
int fib(int n) {
static int cache[48] = {0}; // should be enough to hold all int fibs
if(n < 2) return n; // initial conditions
else if(cache[n]) return cache[n]; // a value already computed and memoized
else return cache[n] = fib(n - 1) + fib(n - 2); // the largest so far
}应该会把计算速度提高，呃，一些因素。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50594593
复制相关文章
相似问题
腾讯云开发者
