在传 统的递归中，典型的模式是，你执行第一个递归调用，然后接着调用下一个递归来计算结果。这种方式中途你是得不到计算结果，知道所有的递归调用都返回。 这样虽然很大程度上简洁了代码编写，但是让人很难它跟高效联系起来。因为随着递归的深入，之前的一些变量需要分配堆栈来保存。
尾递归相对传统递归，其是一种特列。在尾递归中，先执行某部分的计算，然后开始调用递归，所以你可以得到当前的计算结果，而这个结果也将作为参数传入下一 次递归。这也就是说函数调用出现在调用者函数的尾部，因为是尾部，所以其有一个优越于传统递归之处在于无需去保存任何局部变量，从内存消耗上，实现节约特 性。
也许需要一个实例来展示尾递归的独特之处：
考虑一个简单的函数：例如 sum(5)= 1 + 2 +3 + 4 + 5 =15
这里我们用Python来实现：

def recsum(x):
    if x==1:
        return x
    else:
        return x+recsum(x-1)

如果我们执行recsum(5)，那么编译器就执行：

recsum(5)
5+recsum(4)
5+(4+recsum(3))
5+(4+(3+recsum(2)))
5+(4+(3+(2+recsum(1))))
5+(4+(3+(2+1)))
15

注：这里系统需要分配堆栈保存5，4...等值。
接着我们来看看尾递归的实现：
def tailrecsum(x,total =0):
    if x == 0:
        return total
    else:
        return tailrecsum(x-1,total+x)

Python的解释器到底做了哪些工作呢？

tailrecsum(5,0)
tailrecsum(4,5)
tailrecsum(3,9)
tailrecsum(2,12)
tailrecsum(1,14)
tailrecsum(0,15)
15

 你可以看到当前时刻的计算值作为第二个参数传入下一个递归，使得系统不再需要保留之前计算结果。
尾递归的优势就显而易见了。

    再仔细看看，你会发现其实尾递归本质上等价于迭代。如果把之前的那个函数计算写成迭代形式:
def loopsum(x):
    i,result = 1,0
    while i <= x:
        result += i
        i += 1
    return result

一样的执行结果。优势同样在于内存的消耗和效率问题。接着看看斐波那契数的计算：
def fib(i,current = 0, next =1):
    if i == 0:
        return current
    else:
        return fib(i -1,next,current + next)

但是要突破Python对于递归层次的限制1000的话，还需要做些优化。可以参考：
1. Tail call optimization decorator
2. Tail Recursion in python
3. 浅谈尾递归的优化方式
附上1的代码（万一不能访问了）
## {{{ http://code.activestate.com/recipes/474088/ (r1)
#!/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.
## end of http://code.activestate.com/recipes/474088/ }}}