登录  /  注册
博主信息
博文 63
粉丝 2
评论 0
访问量 158240
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
理解递归思想
书声的博客
原创
2032人浏览过

什么是递归
递归(Recursion),指在函数的定义中使用函数自身的方法,即程序的自身调用。

递归一词还较常用于描述以自相似方法重复事物的过程。例如,当两面镜子相互之间近似平行时,镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。   <!--more-->     

递归算法的特点
递归就是方法里调用自身。   

出口:在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。   

效率:递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。   

栈溢出:在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等,所以一般不提倡用递归算法设计程序。   

递归程序的基本步骤
1.初始化算法。递归程序通常需要一个开始时使用的种子值(seed value)。要完成此任务,可以向函数传递参数,或者提供一个入口函数, 这个函数是非递归的,但可以为递归计算设置种子值。1

2.检查要处理的当前值是否已经与基线条件相匹配。如果匹配,则进行处理并返回值。     

3.使用更小的或更简单的子问题(或多个子问题)来重新定义答案。   

4.对子问题运行算法。   

5.将结果合并入答案的表达式。   

6.返回结果。    总结流程:初始化——检查当前值与基线条件的匹配——化小重定义——对子问题运行算法——结果归总——返回结果     

递归与循环的比较
Properties Loops Recursive functions

重复  
    为了获得结果,反复执行同一代码块;以完成代码块或者执行 continue 命令信号而实现重复执行。
    为了获得结果,反复执行同一代码块;以反复调用自己为信号而实现重复执行。
终止条件 
    为了确保能够终止,循环必须要有一个或多个能够使其终止的条件,而且必须保证它能在某种情况下满足这些条件的其中之一。
     为了确保能够终止,递归函数需要有一个基线条件,令函数停止递归。
 状态 
     循环进行时更新当前状态。 
     当前状态作为参数传递。


例子


例子
计算阶乘n! = 1 x 2 x 3 x ... x n,用函数fact(n)表示:  

 def fact(n):                
      if n == 1:
          return 1
      return n * fact(n - 1)


尾递归--解决栈溢出
栈溢出:使用递归函数需要注意防止栈溢出。在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出。 

尾递归(tail-call)优化:在尾部进行函数调用时使用下一个栈结构覆盖当前栈结构,同时保持原来的返回地址。 

本质是对栈进行处理,删掉活动记录(activation record),在函数返回的时候,调用自身本身,并且return语句不能包含表达式。这样,编译器或者解释器就可以把尾递归做优化,使递归本身无论调用多少次,都只占用一个栈帧,不会出现栈溢出的情况。

要使调用成为真正的尾部调用,在尾部调用函数返回前,对其结果不能执行任何其他操作。   

不管递归有多深,栈大小保持不变。尾递归属于线性递归的子集。    用尾递归优化改造上面的阶乘算法,主要是要把每一步的乘积传入到递归函数中: 

def fact(n):
      return fact_iter(n, 1)
  
  def fact_iter(num, product):
      if num == 1:
          return product
      return fact_iter(num - 1, num * product)

可以看到,return fact_iter(num - 1, num * product)仅返回递归函数本身,num - 1和num * product在函数调用前就会被计算,不影响函数调用。可以看到,return fact_iter(num - 1, num * product)仅返回递归函数本身,num - 1和num * product在函数调用前就会被计算,不影响函数调用。

尾递归事实上和循环是等价的,没有循环语句的编程语言只能通过尾递归实现循环。
---------------------
作者:花生酱Scarlett
来源:CSDN
原文:https://blog.csdn.net/ScarlettYellow/article/details/80458856
版权声明:本文为博主原创文章,转载请附上博文链接!

本博文版权归博主所有,转载请注明地址!如有侵权、违法,请联系admin@php.cn举报处理!
全部评论 文明上网理性发言,请遵守新闻评论服务协议
0条评论
作者最新博文
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号

  • 登录PHP中文网,和优秀的人一起学习!
    全站2000+教程免费学