首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >在本例中,如何仅打印一次序列?(递归函数)

在本例中,如何仅打印一次序列?(递归函数)
EN

Stack Overflow用户
提问于 2018-05-30 08:01:39
回答 2查看 66关注 0票数 0

这只是一个斐波那契算法,我如何打印每个斐波纳契数列而不重复每一步?

递归函数在任何方面都是一个很好的用途吗?我知道它更易读,但是如果我把n= 40,在这个简单的算法中有一个明显的延迟,而迭代的方式是瞬时的。

代码语言:javascript
复制
int fib(int n)
{   
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }

    return fib(n - 1) + fib(n - 2);
}
EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2018-05-30 12:08:15

像C这样的命令式语言并不总是很好地映射到算法的函数定义。

非递归通常更快,因为编译器和处理器都可以更容易地优化/并行执行,并且您不会浪费精力,不会不必要地推送和弹出堆栈。无论哪种方式,您只需要前两个fib值来计算下一个值:

代码语言:javascript
复制
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高效地实现算法是另一回事。然而,对于像斐波那契这样简单的东西,我不会使用递归,但不管怎样,这里有一个:

代码语言:javascript
复制
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代码的问题是,它毫无理由地消耗能量和堆栈空间。要以正确的顺序打印值,而无需事先计算和存储每个值,唯一的方法就是更改算法。

票数 0
EN

Stack Overflow用户

发布于 2018-05-30 08:48:45

您可以通过记忆已计算的值来轻松优化递归解决方案:

代码语言:javascript
复制
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
}

应该会把计算速度提高,呃,一些因素。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/50594593

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档