尾部递归优化,递归算法经典实例python

  尾部递归优化,递归算法经典实例python

  本文开头和结尾主要介绍了Python递归优化的实现实例。有需要的朋友可以借鉴一下,希望能有所帮助。祝大家进步很大,早日升职加薪。

  00-1010一般递归和尾部递归一般递归3360尾部递归C中尾部递归的优化Python开放式尾部递归优化

  

目录

  

一般递归与尾递归

  def normal_recursion(n):

  如果n==1:

  返回1

  else:

  return n normal_recursion(n-1)

  执行:

  正规递归(5)

  5正规_递归(4)

  5 4正规_递归(3)

  5 4 3正规递归(2)

  5 4 3 2正规递归(1)

  5 4 3 3

  5 4 6

  5 10

  15

  可以看到,一般的递归,每一级递归都会产生新的局部变量,必须创建新的调用栈。随着递归深度的增加,创建的栈越来越多,导致栈爆炸?

  

一般递归:

  递归基于函数的尾部调用。每一级调用直接返回递归函数更新调用栈,不产生新的局部变量,类似于迭代3360的实现。

  def tail_recursion(n,total=0):

  如果n==0:

  退货总额

  else:

  return tail_recursion(n-1,共n)

  执行:

  tail_recursion(5,0)

  tail_recursion(4,5)

  tail_recursion(3,9)

  tail_recursion(2,12)

  tail_recursion(1,14)

  tail_recursion(0,15)

  15

  可以看出尾递归的每个递归函数的调用都变成了‘线性’。这时候我们可以想,虽然尾递归调用也会创建一个新的栈,但是我们可以优化一下,让每一级尾递归调用共享一个栈!这样就可以解决堆栈爆炸和递归深度限制的问题了!

  

尾递归

  Gcc使用-O2参数来开始尾部递归优化3360

  int tail_recursion(int n,int total) {

  if (n==0) {

  返回总数;

  }

  否则{

  return tail_recursion(n-1,共n);

  }

  }

  int main(void) {

  int total=0,n=4;

  tail_recursion(n,total);

  返回0;

  }

  拆卸

  $ gcc-S tail _ recursion . c-o normal _ recursion。S

  $ gcc-s-o2tail _ recursion . c-otail _ recursion . s gcc启动尾部递归优化

  反汇编代码比较如下(ATT语法,左图优化)

  可以看到,在开始尾部递归优化之前,使用call call函数创建了一个新的调用栈(lbb 0 _ 3);但是开启尾部递归优化后,不会产生新的调用栈,而是直接返回pop bp指向的_tail_recursion函数(pushq %rbp)的地址,仍然使用同一个调用栈!

  

C中尾递归的优化

  Cpython本身不支持尾部递归优化,但有一个很好的解决方案:

  实现一个tail_call_optimized装饰器

  ="brush:py;">#!/usr/bin/env python2.4

  # This program shows off a python decorator(

  # which implements tail call optimization. It

  # does this by throwing an exception if it is

  # its own grandparent, and catching such

  # exceptions to recall the stack.

  import sys

  class TailRecurseException:

   def __init__(self, args, kwargs):

   self.args = args

   self.kwargs = kwargs

  def tail_call_optimized(g):

   """

   This function decorates a function with tail call

   optimization. It does this by throwing an exception

   if it is its own grandparent, and catching such

   exceptions to fake the tail call optimization.

   This function fails if the decorated

   function recurses in a non-tail context.

   """

   def func(*args, **kwargs):

   f = sys._getframe()

   if f.f_back and f.f_back.f_back \

   and f.f_back.f_back.f_code == f.f_code:

   # 抛出异常

   raise TailRecurseException(args, kwargs)

   else:

   while 1:

   try:

   return g(*args, **kwargs)

   except TailRecurseException, e:

   args = e.args

   kwargs = e.kwargs

   func.__doc__ = g.__doc__

   return func

  @tail_call_optimized

  def factorial(n, acc=1):

   "calculate a factorial"

   if n == 0:

   return acc

   return factorial(n-1, n*acc)

  print factorial(10000)

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

  

sys._getframe([depth]):
Return a frame object from the call stack.
If optional integer depth is given, return the frame object that many calls below the top of the stack.
If that is deeper than the call stack, ValueEfror is raised. The default for depth is zero,
returning the frame at the top of the call stack.

  即返回depth深度调用的栈帧对象.

  

import sys

  def get_cur_info():

   print sys._getframe().f_code.co_filename # 当前文件名

   print sys._getframe().f_code.co_name # 当前函数名

   print sys._getframe().f_lineno # 当前行号

   print sys._getframe().f_back # 调用者的帧

  更多关于sys._getframe的使用请看https://www.jb51.net/article/181387.htm

  说一下tail_call_optimized实现尾递归优化的原理:

  当递归函数被该装饰器修饰后, 递归调用在装饰器while循环内部进行, 每当产生新的递归调用栈帧时:f.f_back.f_back.f_code == f.f_code:, 就捕获当前尾调用函数的参数, 并抛出异常, 从而销毁递归栈并使用捕获的参数手动调用递归函数. 所以递归的过程中始终只存在一个栈帧对象, 达到优化的目的.

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

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

  

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

  

  通过pudb右边栏的stack, 可以很清晰的看到调用栈的变化.
因为实现了尾递归优化, 所以factorial(10000)都不害怕递归深度限制报错啦!

  以上就是Python开启尾递归优化实现示例的详细内容,更多关于Python尾递归优化!的资料请关注盛行IT软件开发工作室其它相关文章!

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

相关文章阅读

  • c语言递归法求汉诺塔,汉诺塔递归算法c++语言
  • c语言递归法求汉诺塔,汉诺塔递归算法c++语言,C语言超详细讲解递归算法汉诺塔
  • javan的阶乘的递归算法,递归算法实现阶乘
  • javan的阶乘的递归算法,递归算法实现阶乘,Java算法之递归算法计算阶乘
  • 用递归法求汉诺塔问题Python,汉诺塔递归算法编程
  • 递归算法经典实例,递归算法一般利用什么实现
  • 深度优先搜索的递归算法,设计一个程序实现深度优先搜索(使用递归算法)
  • 汉诺塔问题递归算法实现过程,使用递归方法实现汉诺塔问题的求解编程
  • Python二分查找算法,二分查找非递归算法
  • 迭代算法与递归算法,简述迭代和递归的区别
  • python递归函数例子,Python递归算法经典实例
  • 递归算法和经典递归例子,递归函数python例子
  • python中递归程序,所有递归程序都可以用非递归算法实现
  • 最简单的递归算法c语言举例,递归算法经典实例c语言
  • 递归算法复杂度分析步骤,递归算法的时间复杂度和空间复杂度
  • 留言与评论(共有 条评论)
       
    验证码: