python中尾递归用法实例详解

   这篇文章主要介绍了python中尾递归用法,较为详细的分析了尾递归原理与相关使用技巧,非常具有实用价值,需要的朋友可以参考下

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

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

  原理:

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

  代码:

  ?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

# 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程序设计有所帮助。

时间: 2024-12-21 00:05:49

python中尾递归用法实例详解的相关文章

Java中的instanceof关键字在Android中的用法实例详解_java

在下面介绍Android中如何使用instanceof关键字开发更方便时,先来温习一下java中instanceof的概念. instanceof大部分的概念是这样定义的:instanceof是Java的一个二元操作符,和==,>,<是同一类东西.由于它是由字母组成的,所以也是Java的保留关键字.它的作用是测试它左边的对象是否是它右边的类的实例,返回boolean类型的数据.举个栗子: String s = "I AM an Object!"; boolean isObj

python time模块用法实例详解_python

本文详细讲述了python的内嵌time模块的用法.分享给大家供大家参考之用.具体分析如下:   一.简介 time模块提供各种操作时间的函数 说明:一般有两种表示时间的方式: 第一种是时间戳的方式(相对于1970.1.1 00:00:00以秒计算的偏移量),时间戳是惟一的 第二种以数组的形式表示即(struct_time),共有九个元素,分别表示,同一个时间戳的struct_time会因为时区不同而不同 year (four digits, e.g. 1998) month (1-12) da

js中this用法实例详解_javascript技巧

本文实例讲述了js中this用法.分享给大家供大家参考.具体如下: 1. 指向window 全局变量 alert(this) //返回 [object Window] 全局函数 function sayHello(){ alert(this); } sayHello(); 2. 指向该对象(在全局里面this指向window,在某个对象里面this指向该对象,在闭包里面this指向window) var user="the Window"; var box={ user:'the bo

Python中的闭包实例详解_python

一般来说闭包这个概念在很多语言中都有涉及,本文主要谈谈python中的闭包定义及相关用法.Python中使用闭包主要是在进行函数式开发时使用.详情分析如下: 一.定义 python中的闭包从表现形式上定义(解释)为:如果在一个内部函数里,对在外部作用域(但不是在全局作用域)的变量进行引用,那么内部函数就被认为是闭包(closure).这个定义是相对直白的,好理解的,不像其他定义那样学究味道十足(那些学究味道重的解释,在对一个名词的解释过程中又充满了一堆让人抓狂的其他陌生名词,不适合初学者).下面

Python回调函数用法实例详解

  本文实例讲述了Python回调函数用法.分享给大家供大家参考.具体分析如下: 一.百度百科上对回调函数的解释: 回调函数就是一个通过函数指针调用的函数.如果你把函数的指针(地址)作为参数传递给另一个函数,当这个指针被用为调用它所指向的函数时,我们就说这是回调函数.回调函数不是由该函数的实现方直接调用,而是在特定的事件或条件发生时由另外的一方调用的,用于对该事件或条件进行响应. 二.什么是回调: 软件模块之间总是存在着一定的接口,从调用方式上,可以把他们分为三类:同步调用.回调和异步调用.同步

C#中委托用法实例详解

  本文实例讲述了C#中委托用法.分享给大家供大家参考.具体分析如下: 这里演示了如何使用匿名委托来计算员工的薪水奖金.使用匿名委托简化了程序,因为无需再定义一个单独的方法. (-:The data for each employee is stored in an object containing personal details as well as a delegate that references the algorithm required to calculate the bon

jquery中cookie用法实例详解(获取,存储,删除等)_jquery

本文实例讲述了jquery中cookie用法.分享给大家供大家参考,具体如下: cookie在jquery中有指定的cookie操作类,下面我先来介绍我们在使用cookie操作类时的一些问题,然后介绍正确的使用方法. 使用JQuery操作cookie时 发生取的值不正确的问题: 结果发现cookie有四个不同的属性: 名称,内容,域,路径 $.cookie('the_cookie'); // 读取 cookie $.cookie('the_cookie', 'the_value'); // 存储

js中this用法实例详解

 1. 指向window 全局变量 1 alert(this) //返回 [object Window] 全局函数 1 2 3 4 function sayHello(){ alert(this); } sayHello(); 2. 指向该对象(在全局里面this指向window,在某个对象里面this指向该对象,在闭包里面this指向window) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 var user="the Window";

Python基础之函数用法实例详解_python

本文以实例形式较为详细的讲述了Python函数的用法,对于初学Python的朋友有不错的借鉴价值.分享给大家供大家参考之用.具体分析如下: 通常来说,Python的函数是由一个新的语句编写,即def,def是可执行的语句--函数并不存在,直到Python运行了def后才存在. 函数是通过赋值传递的,参数通过赋值传递给函数 def语句将创建一个函数对象并将其赋值给一个变量名,def语句的一般格式如下: def <name>(arg1,arg2,arg3,--,argN): <stateme