c – 递归函数比非递归函数慢

发布时间：2020-12-16 07:20:48 所属栏目：百科来源：网络整理

导读：我已经使用递归函数作为数字的阶乘和Fibonacci系列(在C中完成),我发现关于阶乘的递归函数正常运行,并且执行速度没有太大差异. 然而在Fibonacci上它是决定性的慢.为什么会这样？递归方法： unsigned long int fib_num(int n) //This is My code{ switch (n)

我已经使用递归函数作为数字的阶乘和Fibonacci系列(在C中完成),我发现关于阶乘的递归函数正常运行,并且执行速度没有太大差异.

然而在Fibonacci上它是决定性的慢.为什么会这样？

递归方法：

unsigned long int fib_num(int n)  //This is My code
{
    switch (n)
    {
    case 1:
        return 0;
        break;
    case 2:
        return 1;
        break;
    default:
        return fib_num(n - 1) + fib_num(n - 2);
        break;
    }
}

迭代方法：

first = 0;
second = 1

for(i = 0; i < num; i++)   
{
    cout<<"n"<<first;

    next = first + second;

    first = second;
    second = next;
}

解决方法

你的观察是正确的,计算中的递归方法,在这种情况下,斐波纳契数,如果仔细观察会导致从一开始就计算斐波那契的每一项,即

例如,要计算F [n] F [n-1],该函数会单独计算两个项,并且它会多次执行相同的作业.

示例：F [5] = F [4] F [3]

要计算F [3]：程序计算：F [2],F [1],F [0]

要计算F [4]：程序再次计算：F [2],F [2],F [0],F [0]和F [3]

以下是您的函数调用将以图形方式显示的内容：

enter image description here

这导致你的观察,即在每次递归调用时,工作量增加一倍,导致复杂度：O(2n).

避免上述情况的一种可能方法是使用memoization：

// header needed for the container: map
#include <map> 

int mem_fact (int i,std::map<int,int>& m)
{
    // if value with key == i does not exist in m: calculate it
    if (m.find(i) == m.end()) 
    {
        // the recursive calls are made only if the value doesn't already exist
        m[i] = mem_fact (i - 1,m) + mem_fact (i - 2,m); 
    }

    // if value with key == i exists,return the corresponding value
    return m[i];
}

int fast_factorial (int i)
{
    // key (Fibonacci index) - value (Fibbonaci number)
    std::map<int,int> memo;

    // initialize the first two Fibonacci numbers
    memo.insert(std::pair<int,int>(0,0));
    memo.insert(std::pair<int,int>(1,1));

    return mem_fact(i,memo);
}

注意：在main()中你需要调用fast_factorial(num_of_fib);

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!