专栏首页深度学习之tensorflow实战篇递归与伪递归区别,Python 实现递归与尾递归

递归与伪递归区别,Python 实现递归与尾递归

      递归函数在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函 数。(1) 递归就是在过程或函数里调用自身。(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。

递归一般用于解决三类问题:

 (1)数据的定义是按递归定义的。(n的阶乘)

   (2)问题解法按递归实现。(回溯)

   (3)数据的结构形式是按递归定义的。(二叉树的遍历,图的搜索)

递归的缺点:

  递归解题相对常用的算法如普通循环等,运行效率较低。因此,应该尽量避免使用递归,除非没有更好的算法或者某种特定情况,递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储,因此递归次数过多容易造成栈溢出。

#递归函数  act(n) = n! = 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n = fact(n-1) x n
def fact(n):
   if n==1:
       return 1
   return n*fact(n-1)

尾递归是指,在函数返回的时候,调用自身本身,并且,return 语句不能包含表达式。这样,编译器或者解释器就可以把尾递归做优化,使递归本身无论调用多少次,都只占用一个栈帧,不会出现栈溢出的情况。

上面的fact(n)函数由于return n * fact(n ‐ 1)引入了乘法表达式,所以就不是尾递归了。要改成尾递归方式,需要多一点代码,主要是要把每一步的乘积传入到递归函数中:

#定义尾递归函数
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)
#测试
print fact_iter(5,1)
120
可以看到,return fact_iter(num ‐ 1, num * product)仅返回递归函数本身,num ‐ 1 和num * product 在函数调用前就会被计算,不影响函数调用。
fact(5)对应的fact_iter(5, 1)的调用如下:
 '''
#实现过程解读
===> fact_iter(5, 1)
===> fact_iter(4, 5)
===> fact_iter(3, 20)
===> fact_iter(2, 60)
===> fact_iter(1, 120)
===> 120
'''

尾递归调用时,如果做了优化,栈不会增长,因此,无论多少次调用也不会导致栈溢出。遗憾的是,大多数编程语言没有针对尾递归做优化,Python 解释器也没有做优化,所以,即使把上面的fact(n)函数改成尾递归方式,也会导致栈溢出。

小结 使用递归函数的优点是逻辑简单清晰,缺点是过深的调用会导致栈溢出。 针对尾递归优化的语言可以通过尾递归防止栈溢出。尾递归事实上和循环是等价的,没有循 环语句的编程语言只能通过尾递归实现循环。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 递归与伪递归区别,Python 实现递归与尾递归

          递归函数在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函 数。(1) 递归就是在过程或函数里调用自身。(2) 在使...

    学到老
  • windows下mysql忘记root密码,如何重设密码

    添加windows下mysql服务 以管理员身份打开cmd,执行 mysqld --install net stop mysql # 忘记密码找回 找到mysq...

    学到老
  • 解决SSH连接linux中文显示乱码问题

    添加windows下mysql服务 以管理员身份打开cmd,执行 mysqld –install net stop mysql

    学到老
  • 递归与伪递归区别,Python 实现递归与尾递归

          递归函数在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函 数。(1) 递归就是在过程或函数里调用自身。(2) 在使...

    学到老
  • Python栈溢出

    python3.5.4 递归函数最恶心的时候莫非栈溢出(Stack overflow)。

    py3study
  • 黑掉美国(英国、澳大利亚、法国等)的交通控制系统

    作者 Taskiller 像电影中那样hacking ? 可能很多读者已经看过电影《虎胆龙威4:虚拟危机》,里面的“黑客恐怖分子”只需要在键盘上按几个按键就可以...

    FB客服
  • MySQL(十四)之数据备份与还原

    前言   上一篇分享了关于MySQL事务的知识,在我们数据库中最重要的就是数据了,所以数据的备份就显的特别的重要!   为什么要备份数据?   在生产环境中我们...

    用户1195962
  • 百万条数据快速查询优化技巧参考

    所以的优化并不是绝对,具体得根据业务实际情况 百万条数据快速查询优化技巧 1.应尽量避免在where子句中使用!=或<>操作符 2.应尽量避免在where子句中...

    逸鹏
  • RxSwift销毁者-dispose源码解析

    现在感觉一切很顺利,但是聪明的我们一定要知道这里落下一个重要的前导因素:什么时候调用了 dispose()

    iOSSir
  • RxSwift 实战操作【注册登录】

    Scott_Mr

扫码关注云+社区

领取腾讯云代金券