Tail recursion in Python

cobrawgl

After spending a lot of time in Scheme, it’s hard not to think in recursion. So recently when I started to improve my Python skills, I missed having Scheme optimize my tail recursive calls.
For example, consider the mutually recursive functions even and odd. You know a number, n, is even if it is 0, or if n - 1 is odd. Similarly, you know a number is not odd if it is 0, and that it is odd if n - 1 is even. This translates to the python code:
def even(x):
  if x == 0:
    return True
  else:
    return odd(x - 1)
def odd(x):
  if x == 0:
    return False
  else:
    return even(x - 1)
This code works, but only for x def tail_rec(fun):
   def tail(fun):
      a = fun
      while type(a) == type(tail):
         a = a()
      return a
   return (lambda x: tail(fun(x)))
def tail_even(x):
  if x == 0:
    return True
  else:
    return (lambda: tail_odd(x - 1))
def tail_odd(x):
  if x == 0:
    return False
  else:
    return (lambda: tail_even(x - 1))
even = tail_rec(tail_even)
odd = tail_rec(tail_odd)
It’s not as pretty as the Scheme version, but it does the trick. Of course, the odd/even functions are just for the sake of a simple example and have no real-world use, but the tail_rec function could be used in practice.


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/78/showart_1891297.html