Python开启尾递归优化!

一般递归与尾递归

一般递归

执行:

可以看到, 一般递归, 每一级递归都需要调用函数, 会创建新的栈,
随着递归深度的增加, 创建的栈越来越多, 造成爆栈💥

尾递归

尾递归基于函数的尾调用, 每一级调用直接返回函数的返回值更新调用栈,而不用创建新的调用栈, 类似迭代的实现, 时间和空间上均优化了一般递归!

执行:

可以看到, 每一级递归的函数调用变成”线性”的形式.

深入理解尾递归

呃, 所以呢? 是不是感觉还不够过瘾… 谁说尾递归调用就不用创建新的栈呢?
还是让我们去底层一探究竟吧

反汇编

  • $ gcc -S tail_recursion.c -o normal_recursion.S
  • $ gcc -S -O2 tail_recursion.c -o tail_recursion.S gcc开启尾递归优化

对比反汇编代码如下(AT&T语法)

可以看到, 开启尾递归优化前, 使用call调用函数, 创建了新的调用栈(LBB0_3);
而开启尾递归优化后, 就没有新的调用栈生成了, 而是直接pop
bp指向的_tail_recursion函数的地址(pushq %rbp)然后返回,

仍旧用的是同一个调用栈!

存在的问题

虽然尾递归优化很好, 但python 不支持尾递归,递归深度超过1000时会报错

一个牛人想出的解决办法

实现一个 tail_call_optimized 装饰器

为了更清晰的展示开启尾递归优化前、后调用栈的变化和tail_call_optimized装饰器抛异常退出递归调用栈的作用, 我这里利用pudb调试工具做了动图

开启尾递归优化前的调用栈

开启尾递归优化后(tail_call_optimized装饰器)的调用栈

通过pudb右边栏的stack, 可以很清晰的看到调用栈的变化.

因为尾递归没有调用栈的嵌套, 所以Python也不会报RuntimeError: maximum recursion depth exceeded错误了!

这里解释一下 sys._getframe() 函数:

更多关于sys._getframe请看Frame Hacks

2 5 收藏 评论

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部