python中尾递归用法实例详解

yipeiwu_com6年前Python基础

本文实例讲述了python中尾递归用法。分享给大家供大家参考。具体分析如下:

如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。

原理:

当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活跃记录而不是在栈中去创建一个新的。编译器可以做到这点,因为递归调用是当前活跃期内最后一条待执行的语句,于是当这个调用返回时栈帧中并没有其他事情可做,因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个,这样所使用的栈空间就大大缩减了,这使得实际的运行效率会变得更高。因此,只要有可能我们就需要将递归函数写成尾递归的形式.

代码:

# This program shows off a python decorator(
# which implements tail call optimization. It
# does this by throwing an exception if it is
# it's 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 it's 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)
# prints a big, big number,
# but doesn't hit the recursion limit.
@tail_call_optimized
def fib(i, current = 0, next = 1):
 if i == 0:
  return current
 else:
  return fib(i - 1, next, current + next)
print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.

希望本文所述对大家的Python程序设计有所帮助。

相关文章

详解Python中如何写控制台进度条的整理

详解Python中如何写控制台进度条的整理

本文实例讲述了Python显示进度条的方法,是Python程序设计中非常实用的技巧。分享给大家供大家参考。具体方法如下: 首先,进度条和一般的print区别在哪里呢? 答案就是print...

Python实现PS滤镜中马赛克效果示例

Python实现PS滤镜中马赛克效果示例

本文实例讲述了Python实现PS滤镜中马赛克效果。分享给大家供大家参考,具体如下: 这里利用 Python 实现PS 滤镜中的马赛克效果,具体的算法原理和效果可以参考附录说明,Pyth...

python和C语言混合编程实例

最近为了测试网速情况怎么样,由于部分业务服务器需要关闭icmp,这样的话采用普通的ping就无法适应我的需求,于是自己简单的写了一个基于tcp端口的ping的程序,由于c执行效率比较的不...

python+requests+unittest API接口测试实例(详解)

python+requests+unittest API接口测试实例(详解)

我在网上查找了下接口测试相关的资料,大都重点是以数据驱动的形式,将用例维护在文本或表格中,而没有说明怎么样去生成想要的用例, 问题: 测试接口时,比如参数a,b,c,我要先测a参数,有(...

Python SqlAlchemy动态添加数据表字段实例解析

Python SqlAlchemy动态添加数据表字段实例解析

本文研究的主要是Python SqlAlchemy动态添加数据表字段,具体如下。 我们知道使用SqlAlchemy创建类来映射数据表,类属性等于数据库字段,但有时候要在我们创建表的时候,...