python中是否可以实现'tail-call elimination'的优化

今天看 python in nutshell 时看到了这段

Reader who are familiar Lisp, Scheme, or functional-programming languages must in particular be aware that Python does not implement the optimization of "tail-call elimination," which is so important in these languages. In Python, any call, recursive or not, has the same cost in terms of both time and memory space, dependent only on the number of arguments: the cost does not change, whether the call is a "tail-call" (meaning that the call is the last operation that the caller executes) or any other, nontail call.

说python中不能实现optimization of "tail-call elimination,"可是我google中搜索了一下发现了这个

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474088

可是由于不太了解functional-programming 　所以the optimization of "tail-call　elimination"　也不知道确切的意思，所以也不知道下面的代码写的对不对。

下面的代码是上面的链接里面的那个人写的.

#!/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 
# 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.

是指“尾递归优化”吧，比如下面的程序

def fib(n):
	if(n==0):
		return 0;
	return tailRecursionFib(n,1,0)

def tailRecursionFib(n, f1, f2):
	if(n==1):
		return f1
	return tailRecursionFib(n-1, f1+f2, f1)

import time
t = time.time()
print "Fibonacci(700)=", fib(700)
print "Total time:", (time.time()*1000-t*1000)

return tailRecursionFib(n-1, f1+f2, f1) 这行递归调用，可以直接优化为跳转指令而不是函数调用（需要保存堆栈），这样速度会快很多，接近于迭代。以前T1讨论过的，很多FP语言都支持这种优化。


e.找到了，见 http://www.iteye.com/post/32289 的最下面

那么python 中可是实现这种优化吗？

那么　象　FP语言 中的尾递归优化　是自动的？还是说要你自己实现？

ps:　论坛现在的搜索好不稳定，经常就什么都搜索不出来了.

优化是编译器/解析器来做的，但是这种风格的代码需要自己来写。

貌似python没有做这优化处理，计算10000就出问题了：

print "Fibonacci(10000)=", fib(10000)
print "Total time:", (time.time()*1000-t*1000)

就会出错了


栈溢出
http://www.iteye.com/t/17585.html

应该是没有优化了

python 中的递归是有　限制的，默认情况下over a depth of 1,000就会抛出异常，可是你还能通过sys模块的setrecursionlimit来设置递归的限制，不过这个设置也是有限制的，它依赖于你的操作系统和c的库，文档里面好像说 大概不会超过 几千层.

呵呵那段代码现在基本能看懂了.

ps:不知道为什么python不把 尾递归优化　加进去，嘿嘿，希望下个版本能加进去.

你给的那段代码：
@tail_call_optimized
标记了这个的function可以被tail_call_optimized这个方法proxy，查看tail_call_optimized(g)，它应该是先判断此方法是否为尾递归类型？我也不太清楚

    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)  

如果是，则执行这个函数，当抛出TailRecurseException时就截获它，然后再次继续执行下去，避免堆栈不够的问题。

    else:   
      while 1:   
        try:   
          return g(*args, **kwargs)   
        except TailRecurseException, e:   
          args = e.args   
          kwargs = e.kwargs   

尾递归方式的函数，执行起来还是跟迭代差不多快的，主要是python不执行这种优化，有stack容量限制，这个proxy就解决它了，比较精妙，收藏一下

呵呵，他这边注释说　This function fails if the decorated 
  function recurses in a non-tail context　。

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)

这段代码我也不懂什么意思
注释也看不太懂

It does this by throwing an exception 
  if it is it's own grandparent

nnd,好郁闷运行了下10000，显卡驱动直接挂掉，无语了.

sys._getframe:


Frame Object:


总算看懂了，
if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code
当属于自身的递归调用（fib()调用fib()）时，上面语句返回true，抛出个 TailRecurseException，然后下面的代码截取异常后直接执行函数。这样就不需要用到堆栈了，也不会溢出。用异常来做控制流啊 多少次递归操作就会抛出多少次异常

if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code

nnd总算我也懂了，原来把and的计算规则忘了，嘿嘿。

x and y ,if x is false 结果就是x 否则结果是　y.

我说python的异常处理是不是开销不大？Java里面可不敢这样搞