对递归和迭代的效率的思考和分析

tolerious 发布于2019-06-28 18:33 / 1166人阅读

摘要：问题斐波那契数列的计算有如下一个数列，，其规则是前两个已知即和，从第个开始，其值为其左边两个值的和此数列称为斐波那契数列。

问题

斐波那契数列的计算：有如下一个数列：1，1, 2, 3, 5, 8, 13, 21，....... 其规则是：前两个已知（即1和2），从第3个开始，其值为其左边两个值的和（此数列称为斐波那契数列）。定义一个函数，该函数可以求出该数列的任意第n个数的值。

递归思想来解决：

递归的本质：函数在其内部调用自身

解决问题时可以将其分拆成若干个小步骤，大问题的解决方法与小步骤方法一致，定义求问题的函数，在需要的位置调用函数即可。

    function fibonacci($n){
      //找出口：什么时候结束递归的调用
      if($n==! || $n==2) return 1;
      
      //计算其他项
      //找入口：什么时候开始递归调用
      return fibonacci($n-1)+fibonacci($n-2);
      
      /**思考
      *return是否可以使用echo替换
      *不可以，因为return  结束函数的调用
      *需要返会给下次递归调用使用
      **/
    }
    $start=microtime(true);//开始计时
    echo fibonacci(35);
    $end=microtime(true);//函数调用结束在计时
    echo "计算耗时".($end-$start)."秒";//4.9秒
    //递归每次调用时，没有立即结束函数的调用，内存没有释放，等到后面计算出结果，才从后面开始释放内存

思考问题：
1.递归：

找入口：

找出口：

2.return是否可以使用echo替换

不可以 return结束函数的调用

需要返回给下次递归调用使用

迭代思想来解决

    function fibonacci($n){
      
      if($n==1 ||$n==2) return 1;
      
      //其他项
      //第三项-->
      //假设求第七项，从第三项考试逐个计算
      //本次计算作为下次计算的条件使用
      
      //定义初始条件
      //前两项作为基本条件
      $first=1;
      $secont=2;
      
      for($i=3;$i<=$n;$i++){
        //之间两项之和
        $res=$first+$second;
        //为后续计算做准备
        //下次计算的第一项来自本次计算计算的第二项
        $first=$second;
        //下次计算的第二项来自本次计算的结果
        $second=$res;
      }
      //循环结束   得到结果
      return $res;
    }
$start=microtime(true);
echo fibonacci(135);
$end=microtime(true);
echo "计算耗时：".($end-$start);//4.315秒，比递归效率高几千万倍

结论：迭代的运行效率比递归高很多，能用迭代解决就别用递归，也就是说先考虑迭代再考虑递归。

云服务器 GPU云服务器对人工智能的思考数据的表示和分析数据的统计和分析云服务器和挖矿的区别 1对1服务

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/28408.html

对递归和迭代的效率的思考和分析

摘要：问题斐波那契数列的计算有如下一个数列，，其规则是前两个已知即和，从第个开始，其值为其左边两个值的和此数列称为斐波那契数列。问题斐波那契数列的计算：有如下一个数列：1，1, 2, 3, 5, 8, 13, 21，....... 其规则是：前两个已知（即1和2），从第3个开始，其值为其左边两个值的和（此数列称为斐波那契数列）。定义一个函数，该函数可以求出该数列的任意第n个数的值。递归...

codeGoogle 2019-08-22 15:26 评论0 收藏0
【C语言】玩转递归——学好递归，你需要掌握的知识！

摘要：所以，递归在编程中同样是很重要的一个知识点。举个例子用递归实现求第个斐波那契数。总结起来四个字大事化小继续举斐波那契数的例子三递归是怎样运行的我们通过一道题目来讲解。 ...

Donne 2021-09-09 09:33 评论0 收藏0
【零基础趣学C语言】- 史上最全C语言函数详解（万字图文+代码演示+图解）

摘要：语言在设计中考虑了函数的高效性和易用性两个原则。在语言中，最常见的当属函数了。以上就是一个函数，它被称为语言的入口函数，或者主函数。例如和都是函数名。形式参数当函数调用完成之后就自动销毁了。 ...

468122151 2021-11-24 09:39 评论0 收藏0
JavaScript中的算法（附10道面试常见算法题解决方法和思路）

摘要：中的算法附道面试常见算法题解决方法和思路关注每日一道面试题详解面试过程通常从最初的电话面试开始，然后是现场面试，检查编程技能和文化契合度。值得记住的数组方法有和。一个好的解决方案是使用内置的方法。 JavaScript中的算法（附10道面试常见算法题解决方法和思路）关注github每日一道面试题详解 Introduction 面试过程通常从最初的电话面试开始，然后是现场面试，检查编程...

Cruise_Chan 2019-08-26 10:22 评论0 收藏0
Python | 递归

摘要：那假如我们用递归来描述这种情况呢定义基本情况其它情形所以在上述求和中的定义又用到了自己本身的定义，这就构成了递归。说起递归，我觉得其实大部分人应该是不陌生的，递归广泛存在于生活中。比如： showImg(https://segmentfault.com/img/remote/1460000007420204?w=294&h=450); The woman in this image ...

qieangel2013 2019-07-31 10:52 评论0 收藏0