##language:zh
#pragma section-numbers off
##含有章节索引导航的 ZPyUG 文章通用模板
<<TableOfContents>>
## 默许导航,请保留
<<Include(ZPyUGnav)>>


= Py尾递归以及优化 =
{{{
lee Alexander <superpowerlee@gmail.com>
sender-time	Sent at 01:57 (GMT+08:00). Current time there: 8:53 AM. ✆
reply-to	python-cn@googlegroups.com
to	python-cn@googlegroups.com
date	Thu, Sep 16, 2010 at 01:57
subject	[CPyUG]一个很Cool的Idear->Python的尾递归优化
}}}

##startInc
 参考::
  * [[http://www.leyond.info/tail-recursion/|尾递归(Tail Recursion)]]
   * [[http://zh-cn.w3support.net/index.php?db=so&id=33923|什么是尾递归？]]
  * [[http://www.phpfans.net/article/htmls/201008/Mjk4MTI4.html|不同的角度，不同的玩法——用Python实现Fibonacci函数]]
   * [[http://bbs.chinaunix.net/archiver/tid-1431193.html|python下lambda+尾递归(页 1) - Python - ChinaUnix.net]]
   * [[http://m.cnblogs.com/34089/1641603.html|博客园手机版-信春哥！Python递归原地满状态变显式堆栈！入教即送尾递归优化！]]
   * [[http://www.cnblogs.com/Alexander-Lee/archive/2010/07/21/1782543.html|浅谈递归过程以及递归的优化 - 懒人居 - Coding for fun]]
   * [[http://code.activestate.com/recipes/474088/|Tail Call Optimization Decorator « Python recipes « ActiveState Code]]
   * [[http://blog.zhaojie.me/2009/04/tail-recursion-explanation.html|浅谈尾递归的优化方式 - 老赵点滴 - 追求编程之美]]

== activestate提议 ==
偶然在国外一个网站瞅到的，非常的酷，发出来共享一下。一般来说，Python和Java，C#一样是没有尾递归自动优化的能力的，递归调用受到调用栈长度的限制被广泛的诟病，但是这个狂人用一个匪夷所思的方法解决了这个问题并在Python上实现了，从此Python的递归调用再也不用受到调用栈长度的制约，太酷了。

 * 首先我们还是从递归说起，之前我发过一篇 《[[http://www.cnblogs.com/Alexander-Lee/archive/2010/07/21/1782543.html|浅谈递归过程以及递归的优化]]》其中用到了斐波那契数来作为例子.线性递归的算法由于太过一低效就被我们Pass掉了，我们先来看尾递过方式的调用：

{{{#!python
def Fib(n,b1=1,b2=1,c=3):
    if n<3:
        return 1
    else:
        if n==c:
            return b1+b2
        else:
            return Fib(n,b1=b2,b2=b1+b2,c=c+1)
}}}
 
这段程序我们来测试一下，调用 Fib(1001)结果：
{{{
>>> def Fib(n,b1=1,b2=1,c=3):

...     if n<3:

...         return 1

...     else:

...         if n==c:

...             return b1+b2

...         else:

...             return Fib(n,b1=b2,b2=b1+b2,c=c+1)

... 

>>> Fib(1001)

70330367711422815821835254877183549770181269836358732742604905087154537118196933
57974224949456261173348775044924176599108818636326545022364710601205337412127386
7339111198139373125598767690091902245245323403501L
 
}}}

如果我们用Fib(1002)，结果，茶几了，如下：
{{{
  .....

  File "<stdin>", line 8, in Fib

  File "<stdin>", line 8, in Fib

  File "<stdin>", line 8, in Fib

  File "<stdin>", line 8, in Fib

  File "<stdin>", line 8, in Fib

  File "<stdin>", line 8, in Fib

RuntimeError: maximum recursion depth exceeded

>>> 
}}}

好了，现在我们来尾递归优化

我们给刚才的Fib函数增加一个Decorator,如下：
{{{#!python
@tail_call_optimized
def Fib(n,b1=1,b2=1,c=3):
    if n<3:
        return 1
    else:
        if n==c:
            return b1+b2
     else:
        return Fib(n,b1=b2,b2=b1+b2,c=c+1)
}}}
 
=== @tail_call_optimized ===
恩，就是这个@tail_call_optimized的装饰器 ，这个装饰器使Python神奇的打破了调用栈的限制。
 * 这下即使我们Fib(20000)，也能在780ms跑出结果（780ms是以前博文提到那台2000元的上网本跑出来的结果）

不卖关子了，下面我们来看看这段神奇的代码：
{{{
#!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.
## end of http://code.activestate.com/recipes/474088/ 
}}}

=== 讨论 ===
使用的方法前面已经展示了，令我感到大开眼界的是，作者用了抛出异常然后自己捕获的方式来打破调用栈的增长，简直是太匪夷所思了。而且效率问题，和直接递归大概增加5倍的时间开销，最后很不可思议的，尾递归优化的目的达成了。
 * 本代码的出处：http://code.activestate.com/recipes/474088/
 *  还有一个JavaScript的实现：http://w3future.com/weblog/2006/02/#tailCallEliminationInJavascript

 讨论::
  * 为了这个目的增加的时间开销值得否？
  * 是否还有其他的更有效率的实现方法？

== 机械唯物主义 ==
{{{
机械唯物主义 : linjunhalida <linjunhalida@gmail.com>
sender-time	Sent at 08:13 (GMT+08:00). Current time there: 9:03 AM. ✆
reply-to	python-cn@googlegroups.com
to	python-cn@googlegroups.com
date	Thu, Sep 16, 2010 at 08:13
}}}
	
如果为了效率, 还是转迭代吧. 这个是比较类似递归的迭代.
{{{#!python
def process(b1, b2, c):
    t = b2
    b2 += b1
    b1 = t
    c += 1
    return b1, b2, c

def fib(n):
    b1, b2, c = 1, 1, 3
    while 1:
        if n<3:
            return 1
        elif n==c:
            return b1+b2
        else:
            b1, b2, c = process(b1, b2, c)
}}}

== Shell Xu 实測 ==
{{{
Shell Xu <shell909090@gmail.com>
sender-time	Sent at 10:34 (GMT+08:00). Current time there: 11:28 AM. ✆
reply-to	python-cn@googlegroups.com
to	python-cn@googlegroups.com
date	Thu, Sep 16, 2010 at 10:34
subject	Re: [CPyUG]一个很Cool的Idear->Python的尾递归优化
}}}

{{{#!python
# -*- coding: utf-8 -*-
# @date: 2010-09-16
# @author: shell.xu
import os
import sys

class TailRecurseException:  
    def __init__(self, args, kwargs):  
        self.args = args  
        self.kwargs = kwargs  
        
def tail_call_optimized(g):  
    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, kwargs = e.args, e.kwargs
    return func

class InnerDt(object):
    def __init__(self, params, kargs):
        self.params, self.kargs = params, kargs

def tail_call(func):
    def inner(*params, **kargs):
        f = sys._getframe()  
        if f.f_back and f.f_back.f_back and\
                f.f_back.f_back.f_code == f.f_code:
            return InnerDt(params, kargs)
        else:
            while 1:
                r = func(*params, **kargs)
                if not isinstance(r, InnerDt): return r
                else: params, kargs = r.params, r.kargs
    return inner

@tail_call_optimized
def Fib(n,b1=1,b2=1,c=3):
    if n<3: return 1
    if n==c: return b1+b2
    return Fib(n,b1=b2,b2=b1+b2,c=c+1)

@tail_call
def Fibr(n,b1=1,b2=1,c=3):
    if n<3: return 1
    if n==c: return b1+b2
    return Fibr(n,b1=b2,b2=b1+b2,c=c+1)

def process(b1, b2, c):
    return b2, b1 + b2, c + 1

def fib1(n):
    b1, b2, c = 1, 1, 3
    while 1:
        if n<3: return 1
        elif n==c: return b1+b2
        else: b1, b2, c = process(b1, b2, c)

def fib2(n):
    if n < 3: return 1
    f1, f2 = 1, 1
    for i in xrange(3, n):
        if i & 1: f1 += f2
        else: f2 += f1
    return f1 + f2

if __name__=='__main__':
    from timeit import Timer
    t = Timer("Fib(10000)", "from __main__ import *")
    tr = Timer("Fibr(10000)", "from __main__ import *")
    t1 = Timer("fib1(10000)", "from __main__ import *")
    t2 = Timer("fib2(10000)", "from __main__ import *")
    print t.timeit(10), tr.timeit(10), t1.timeit(10), t2.timeit(10)
    print Fib(10000) == Fibr(10000), fib1(10000) == fib2(10000), Fib(10000) == fib1(10000)
}}}

{{{
---------------------------------------------------------------------------

c:\Documents and Settings\Administrator\My Documents\note>test.py
<timeit-src>:2: SyntaxWarning: import * only allowed at module level
<timeit-src>:2: SyntaxWarning: import * only allowed at module level
<timeit-src>:2: SyntaxWarning: import * only allowed at module level
<timeit-src>:2: SyntaxWarning: import * only allowed at module level
1.21529047311 4.59827187267 0.325211272378 0.279499038127
True True True

---------------------------------------------------------------------------

Fib(20000)
python -m profile test.py

---------------------------------------------------------------------------

         80000 function calls (60003 primitive calls) in 0.681 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    19998    0.059    0.000    0.059    0.000 :0(_getframe)
        1   -0.001   -0.001    0.674    0.674 :0(execfile)
        1    0.004    0.004    0.004    0.004 :0(setprofile)
        1    0.003    0.003    0.677    0.677 <string>:1(<module>)
        1    0.000    0.000    0.681    0.681 profile:0(execfile('test.py'))
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.000    0.000 test.py:13(tail_call_optimized)
  19998/1    0.337    0.000    0.674    0.674 test.py:14(func)
        1    0.000    0.000    0.000    0.000 test.py:26(InnerDt)
        1    0.000    0.000    0.000    0.000 test.py:30(tail_call)
    19998    0.245    0.000    0.585    0.000 test.py:43(Fib)
        1    0.000    0.000    0.675    0.675 test.py:5(<module>)
        1    0.000    0.000    0.000    0.000 test.py:8(TailRecurseException)
    19997    0.033    0.000    0.033    0.000 test.py:9(__init__)

---------------------------------------------------------------------------

Fibr(20000)
python -m profile test.py

---------------------------------------------------------------------------

         99998 function calls (80001 primitive calls) in 0.677 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    19998    0.038    0.000    0.038    0.000 :0(_getframe)
        1    0.002    0.002    0.673    0.673 :0(execfile)
    19998    0.065    0.000    0.065    0.000 :0(isinstance)
        1    0.004    0.004    0.004    0.004 :0(setprofile)
        1    0.000    0.000    0.673    0.673 <string>:1(<module>)
        1    0.000    0.000    0.677    0.677 profile:0(execfile('test.py'))
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.000    0.000 test.py:13(tail_call_optimized)
        1    0.000    0.000    0.000    0.000 test.py:26(InnerDt)
    19997    0.076    0.000    0.076    0.000 test.py:27(__init__)
        1    0.000    0.000    0.000    0.000 test.py:30(tail_call)
  19998/1    0.247    0.000    0.671    0.671 test.py:31(inner)
    19998    0.244    0.000    0.539    0.000 test.py:49(Fibr)
        1    0.000    0.000    0.671    0.671 test.py:5(<module>)
        1    0.000    0.000    0.000    0.000 test.py:8(TailRecurseException)
}}}
为什么？timeit的测量结果和profile差这么多？

##endInc

----
'''反馈'''

创建 by -- ZoomQuiet [<<DateTime(2010-09-16T09:04:42+0800)>>]