首页 后端开发 Python教程 python中尾递归用法实例详解

python中尾递归用法实例详解

Jun 06, 2016 am 11:26 AM
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程序设计有所帮助。

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热门文章

仓库:如何复兴队友
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.能量晶体解释及其做什么(黄色晶体)
1 周前 By 尊渡假赌尊渡假赌尊渡假赌

热门文章

仓库:如何复兴队友
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.能量晶体解释及其做什么(黄色晶体)
1 周前 By 尊渡假赌尊渡假赌尊渡假赌

热门文章标签

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

怎么下载deepseek 小米 怎么下载deepseek 小米 Feb 19, 2025 pm 05:27 PM

怎么下载deepseek 小米

模板化的优点和缺点有哪些? 模板化的优点和缺点有哪些? May 08, 2024 pm 03:51 PM

模板化的优点和缺点有哪些?

Google AI 为开发者发布 Gemini 1.5 Pro 和 Gemma 2 Google AI 为开发者发布 Gemini 1.5 Pro 和 Gemma 2 Jul 01, 2024 am 07:22 AM

Google AI 为开发者发布 Gemini 1.5 Pro 和 Gemma 2

仅用250美元,Hugging Face技术主管手把手教你微调Llama 3 仅用250美元,Hugging Face技术主管手把手教你微调Llama 3 May 06, 2024 pm 03:52 PM

仅用250美元,Hugging Face技术主管手把手教你微调Llama 3

分享几个.NET开源的AI和LLM相关项目框架 分享几个.NET开源的AI和LLM相关项目框架 May 06, 2024 pm 04:43 PM

分享几个.NET开源的AI和LLM相关项目框架

golang 函数调试与分析的完整指南 golang 函数调试与分析的完整指南 May 06, 2024 pm 02:00 PM

golang 函数调试与分析的完整指南

deepseek怎么问他 deepseek怎么问他 Feb 19, 2025 pm 04:42 PM

deepseek怎么问他

evaluate函数怎么保存 evaluate函数怎么保存 May 07, 2024 am 01:09 AM

evaluate函数怎么保存

See all articles