免费建论坛网站,上海最专业的seo公司,怎么给网站加代码,天津建设工程信息网天津C语言用递归求斐波那契数#xff0c;让你发现递归的缺陷和效率瓶颈 分享到#xff1a;QQ空间新浪微博腾讯微博豆瓣人人网递归是一种强有力的技巧#xff0c;但和其他技巧一样#xff0c;它也可能被误用。一般需要递归解决的问题有两个特点#xff1a;存在限制条件#xf…C语言用递归求斐波那契数让你发现递归的缺陷和效率瓶颈 分享到QQ空间新浪微博腾讯微博豆瓣人人网 递归是一种强有力的技巧但和其他技巧一样它也可能被误用。 一般需要递归解决的问题有两个特点 存在限制条件当符合这个条件时递归便不再继续每次递归调用之后越来越接近这个限制条件。 递归使用最常见的一个例子就是求阶乘具体描述和代码请看这里C语言递归和迭代法求阶乘 但是递归函数调用将涉及一些运行时开销——参数必须压到堆栈中为局部变量分配内存空间所有递归均如此并非特指求阶乘这个例子寄存器的值必须保存等。当递归函数的每次调用返回时上述这些操作必须还原恢复成原来的样子。所以 基于这些开销对于递归求阶乘而言它并没有简化问题的解决方案。 迭代求阶乘使用简单循环的程序看上去不甚符合前面阶乘的数学定义但它却能更为有效地计算出结果。如果你仔细观察递归函数你会发现递归调用是函数所执行的最后一项任务。这个函数是尾部递归(tail recursion)的一个例子。由于函数在递归调用返回之后不再执行任何任务所以尾部递归可以很方便地转换成一个简单循环完成相同的任务。 提示许多问题是以递归的形式进行解释的这只是因为它比非递归形式更为清晰。但是这些问题的迭代实现往往比递归实现效率更高虽然代码的可读性可能稍差一些当一个问题相当复杂难以用迭代形式实现时此时递归实现的简洁性便可以补偿它所带来的运行时开销。 这里有一个更为极端的例子菲波那契数就是一个数列数列中每个数的值就是它前面两个数的和。 这种关系常常用递归的形式进行描述 同样这种递归形式的定义容易诱导人们使用递归形式来解决问题。这里有一个陷牌它使用递归步骤计算Fibonacci(n-1)和Fibonacci(n-2)。但是在计算Fibonacci(n-1)时也将计算Fibonacci(n-2)。这个额外的计算代价有多大呢 答案是它的代价远远不止一个冗余计算每个递归调用都触发另外两个递归调用而这两个调用的任何一个还将触发两个递归调用再接下去的调用也是如此。这样冗余计算的数量增长得非常快。例如在递归计算Fibonacci(10)时Fibonacci(3)的值被计算了21次。但是在递归计算 Fibonacci(30)时Fibonacci(3)的值被计算了317811次。当然这317811次计算所产生的结果是完全一样的除了其中之一外其余的纯属浪费。这个额外的开销真是相当恐怖 如果使用一个简单循环来代替递归这个循环的形式肯定不如递归形式符合前面菲波那契数的抽象定义但它的效率提高了几十万倍 当你使用递归方式实现一个函数之前先问问你自己使用递归带来的好处是否抵得上它的代价。 而且你必须小心这个代价可能比初看上去要大得多。 不信请看下面的代码分别用递归和迭代计算斐波那契数效率差距真是大的惊人。 复制纯文本复制 #include stdio.h#include time.h#include windows.h // 递归计算斐波那契数long fibonacci_recursion( int n ){ if( n 2 ) return 1; return fibonacci_recursion(n-1) fibonacci_recursion(n-2);} // 迭代计算斐波那契数long fibonacci_iteration( int n ){ long result; long previous_result; long next_older_result; result previous_result 1; while( n 2 ){ n - 1; next_older_result previous_result; previous_result result; result previous_result next_older_result; } return result;} int main(){ int N 45; // 递归消耗的时间 clock_t recursion_start_time clock(); long result_recursion fibonacci_recursion(N); clock_t recursion_end_time clock(); // 迭代消耗的时间 clock_t iteration_start_time clock(); long result_iteration fibonacci_iteration(N); clock_t iteration_end_time clock(); // 输出递归消耗的时间 printf(Result of recursion: %ld \nTime: %fseconds, fibonacci_recursion(N), (double)(recursion_end_time-recursion_start_time)/CLOCKS_PER_SEC ); printf(\n-----------------------\n); // 输出迭代消耗的时间 printf(Result of iteration: %ld \nTime: %fseconds, fibonacci_iteration(N), (double)(iteration_end_time-iteration_start_time)/CLOCKS_PER_SEC ); return 0;} #include stdio.h
#include time.h
#include windows.h// 递归计算斐波那契数
long fibonacci_recursion( int n )
{if( n 2 )return 1;return fibonacci_recursion(n-1) fibonacci_recursion(n-2);
}// 迭代计算斐波那契数
long fibonacci_iteration( int n )
{long result;long previous_result;long next_older_result;result previous_result 1;while( n 2 ){n - 1;next_older_result previous_result;previous_result result;result previous_result next_older_result;}return result;
}int main(){int N 45;// 递归消耗的时间clock_t recursion_start_time clock();long result_recursion fibonacci_recursion(N);clock_t recursion_end_time clock();// 迭代消耗的时间clock_t iteration_start_time clock();long result_iteration fibonacci_iteration(N);clock_t iteration_end_time clock();// 输出递归消耗的时间printf(Result of recursion: %ld \nTime: %fseconds,fibonacci_recursion(N),(double)(recursion_end_time-recursion_start_time)/CLOCKS_PER_SEC);printf(\n-----------------------\n);// 输出迭代消耗的时间printf(Result of iteration: %ld \nTime: %fseconds,fibonacci_iteration(N),(double)(iteration_end_time-iteration_start_time)/CLOCKS_PER_SEC);return 0;
} 运行结果 Result of recursion: 1134903170
Time: 7.494000 seconds
---------------------------------------
Result of iteration: 1134903170
Time: 0.000000 seconds 注意上面的程序最好在GCCLinux下的GCC或Windows下的Code:Blocks下运行VC下可能统计不到运行时间。 看吧用递归花了将近7.5秒的时间但是用迭代几乎不费吹灰之力效率快到统计不到运行时间。
