• 网站首页
  • 股票
  • 美股
  • 港股
  • 沪指
  • 基金
  • 私募
  • 理财
  • 信托
  • P2P
  • 递归算法 你为什么学不会递归?读完这篇文章轻松理解递归算法

    发布时间: 2019-11-20作者:球皇直播阅读(3057)

    递归算法递归算法你为什么学不会递归?读完这篇文章轻松理解递归算法:递归算法对于很多编程初学者来说,递归算法是学习语言的最大障碍之一。很多人也是半懂不懂,结果学到很深的境地也会因为自己基

    递归算法

    对于很多编程初学者来说,递归算法是学习语言的最大障碍之一。很多人也是半懂不懂,结果学到很深的境地也会因为自己基础不好,导致发展太慢。

    可能也有一大部分人知道递归,也能看的懂递归,但在实际做题过程中,却不知道怎么使用。今天,我们就来说一说递归算法的使用。

    什么是递归

    递归,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。也就是说,递归算法是一种直接或者间接调用自身函数或者方法的算法。

    通俗来说,递归算法的实质是把问题分解成规模缩小的同类问题的子问题,然后递归调用方法来表示问题的解。

    递归的基本原理

    第一:每一级的函数调用都有自己的变量。

    第二:每一次函数调用都会有一次返回。

    第三:递归函数中,位于递归调用前的语句和各级被调用函数具有相同的执行顺序。

    第四:递归函数中,位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反。

    第五:虽然每一级递归都有自己的变量,但是函数代码并不会得到复制。

    递归的优缺点

    递归的三大要素

    第一要素:明确你这个函数想要干什么。先不管函数里面的代码什么,而是要先明白,你这个函数的功能是什么,要完成什么样的一件事。

    第二要素:寻找递归结束条件。我们需要找出当参数为啥时,递归结束,之后直接把结果返回,请注意,这个时候我们必须能根据这个参数的值,能够直接知道函数的结果是什么。

    第三要素:找出函数的等价关系式。我们要不断缩小参数的范围,缩小之后,我们可以通过一些辅助的变量或者操作,使原函数的结果不变。

    递归的过程

    具体地说,如果递归函数调用自己,则被调用的函数也将调用自己,这将无限循环下去,除非代码中包含终止调用链的内容。通常的方法将递归调用放在if语句中。例如,void类型的递归函数recurs()的代码如下:

    用文字再现这段代码块的内容:

    只要if语句为true,每个recurs()调用都将执行statement1,然后再调用recurs(),而不会执行statements2 。当前调用结束后,程序控制权将返回给调用它的recurs(),而该recurs()将执行其statements2部分,然后结束,并将控制权返回给前一个调用,依次类推。

    递归的使用

    递归的强大之处在于它允许用户用有限的语句描述无限的对象。因此,在计算机科学中,递归可以被用来描述无限步的运算,尽管描述运算的程序是有限的。 这一点是循环不太容易做到的。

    编写正确的递归算法,一定要有 ”归“ 的步骤,也就是说递归算法,在分解问题到不能再分解的步骤时,要让递归有退出的条件,否则就会陷入死循环,最终导致内存不足引发栈溢出异常。

    下面,我们通过两个例子来学习一下,递归的使用:

    例一:递归求阶乘

    例二:递归求斐波那契数列

    从上面的步骤我们可以清晰的看到递归算法的第一步是分治,把复杂的大的问题,给拆分成一个一个小问题,直到不能再拆解,通过退出条件retrun,然后再从最小的问题开始解决,只到所有的子问题解决完毕,那么最终的大问题就迎刃而解。

    递归的优化方法

    递归问题中想到思路本身不非常难,真正的难点在于如何优化。

    1考虑是否重复计算

    如果你使用递归的时候不进行优化,是有非常非常非常多的子问题被重复计算的。因此,使用递归的时候,必要须要考虑有没有重复计算,如果重复计算了,一定要把计算过的状态保存起来。

    2、考虑尾递归

    对于递归的问题,我们一般都是从上往下递归的,直到递归到最底,再一层一层着把值返回。

    不过,有时候当 n 比较大的时候,例如当 n = 10000 时,那么必须要往下递归10000层直到 n <=1 才将结果慢慢返回,如果n太大的话,可能栈空间会不够用。这个时候,就可以用尾递归优化来解决。

    顾名思义,尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量。直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去。

    有的人刚接触算法的时候,一直都惧怕递归,也很少或者说几乎就不写递归的代码。但其实学习了以后,发现递归还是挺可爱的。就像在数学找一组数字的规律一样,可以锻炼我们的思维。希望这篇文章,能额昂你有所收获。

    递归算法
    递归算法递归算法你为什么学不会递归?读完这篇文章轻松理解递归算法:递归算法对于很多编程初学者来说,递归算法是学习语言的最大障碍之一。很多人也是半懂不懂,结果学到很深的境地也会因为自己基

    网站首页 - 股票 - 美股 - 港股 - 沪指 - 基金 - 私募 - 理财 - 信托 - P2P - 地图

    厦门财经[www.026xm.com]厦门财经网是厦门新闻门户网,每天发布财经信息!股市行情,服务与厦门百姓息息相关的理财生活.通过厦门财经网让更多人了解厦门,让厦门本土更好的了解本地资讯。

    未经本站书面特别授权,请勿转载或建立镜像

    厦门财经网,厦门财经,财经网,财经网站,国际财经网,财经网址,财经网络,专业财经网站,东南财经网

    Copyright © 2004 - 2018 www.026xm.com Co. All Rights Reserved 厦门财经 版权所有