8.python lambda和递归函数

一、lambda函数

lambda 函数是一种快速定义单行的最小函数，是从 Lisp 借用来的，可以用在任何需要函数的地方 。

• 1. 下面的例子比较了传统的函数定义def与lambda定义方式：

>>> def f ( x ,y):
...   return x * y
...
>>> f ( 2,3 )
6
>>> g = lambda x ,y: x * y
>>> g ( 2,3 )
6

可以看到，两个函数得到的结果一样，而对于实现简单功能的函数来说，使用lambda函数来定义更加精简灵活，还可以直接把函数赋值给一个变量，用变量名来表示函数名。
其实lambda函数在很多时候都是不需要赋值给一个变量的。

• 2. 使用lambda函数还有一些注意事项：
  • 1. lambda 函数可以接收任意多个参数 (包括可选参数) 并且返回单个表达式的值。
  • 2. lambda 函数不能包含命令，包含的表达式不能超过一个。
  • 3. lambda语句用来创建函数对象。本质上，lambda需要一个参数，后面仅跟单个表达式作为函数体，而表达式的值被这个新建的函数返回。注意，即便是print语句也不能用在 lambda形式中，只能使用表达式。
• 3. def 与lambda的区别
  • 1. lambda是在python中使用lambda来创建匿名函数，而用def创建的方法是有名称的。
  • 2. lambda会创建一个函数对象，但不会把这个函数对象赋给一个标识符，而def则会把函数对象赋值给一个变量。
  • 3. lambda它只是一个表达式，而def则是一个语句。因为def是语句，不是表达式不能嵌套在里面，lambda表达式在“：”后只能有一个表达式。也就是说，在def中，用return可以返回的也可以放在lambda后面，不能用return返回的也不能定义在python lambda后面。因此，像if或for或print这种语句就不能用于lambda中，lambda一般只用来定义简单的函数。
• 4.实例

class People :
  age = 0
  gender = 'male'

  def __init__ ( self , age , gender ):
    self . age = age
    self . gender = gender

  def toString ( self ):
    return 'Age:' + str ( self . age ) + ' /t Gender:' + self . gender

List = [ People (21 , 'male'), People (20 , 'famale'), People (34 , 'male'),  \
People (19 , 'famale')]
print 'Befor sort:'
for p in List :
  print p . toString ()

List . sort ( lambda p1 , p2 : cmp ( p1 . age , p2 . age ))

print ' /n After ascending sort:'
for p in List :
  print p . toString ()

List . sort ( lambda p1 , p2 : - cmp ( p1 . age , p2 . age ))
print ' /n After descending sort:'
for p in List :
  print p . toString ()

二、递归函数

• 1. 定义
  在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。

• 2. 递归特性

  1. 记住所有的递归函数都有一个退出条件
  2. 相邻两次重复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）。
  3. 递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）
  4. 递归的层数在python里是有限制的 997/998层，可以使用sys模块对递归层数进行修改sys.setrecursionlimit(10000000)。

• 3. 实例详解

  • 1. 计算阶乘n! = 1 x 2 x 3 x ... x n
       fact(n)可以表示为n x fact(n-1)，只有n=1时需要特殊处理。

def fact(n):
  if n==1:
    return 1
  return n * fact(n - 1)

如果我们计算fact(5)，可以根据函数定义看到计算过程如下：

===> fact(5)
===> 5 * fact(4)
===> 5 * (4 * fact(3))
===> 5 * (4 * (3 * fact(2)))
===> 5 * (4 * (3 * (2 * fact(1))))
===> 5 * (4 * (3 * (2 * 1)))
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
===> 120

递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。
使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。可以试试fact(1000)：

>>> fact(1000)
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
 File "<stdin>", line 4, in fact
 ...
 File "<stdin>", line 4, in fact
RuntimeError: maximum recursion depth exceeded

解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。

尾递归是指，在函数返回的时候，调用自身本身，并且，return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。

上面的fact(n)函数由于return n * fact(n - 1)引入了乘法表达式，所以就不是尾递归了。要改成尾递归方式，需要多一点代码，主要是要把每一步的乘积传入到递归函数中：

def fact(n):
  return fact_iter(1, 1, n)
 
def fact_iter(product, count, max):
  if count > max:
    return product
  return fact_iter(product * count, count + 1, max)

可以看到，return fact_iter(product * count, count + 1, max)仅返回递归函数本身，product * count和count + 1在函数调用前就会被计算，不影响函数调用。
fact(5)对应的fact_iter(1, 1, 5)的调用如下：

===> fact_iter(1, 1, 5)
===> fact_iter(1, 2, 5)
===> fact_iter(2, 3, 5)
===> fact_iter(6, 4, 5)
===> fact_iter(24, 5, 5)
===> fact_iter(120, 6, 5)
===> 120

尾递归调用时，如果做了优化，栈不会增长，因此，无论多少次调用也不会导致栈溢出。

遗憾的是，大多数编程语言没有针对尾递归做优化，Python解释器也没有做优化，所以，即使把上面的fact(n)函数改成尾递归方式，也会导致栈溢出。

有一个针对尾递归优化的decorator，可以参考源码：

http://code.activestate.com/recipes/474088-tail-call-optimization-decorator/

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

我们后面会讲到如何编写decorator。现在，只需要使用这个@tail_call_optimized，就可以顺利计算出fact(1000)：

>>> fact(1000)
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

• 4. 总结
  • 1. 使用递归函数的优点是逻辑简单清晰，缺点是过深的调用会导致栈溢出。
  • 2. 针对尾递归优化的语言可以通过尾递归防止栈溢出。尾递归事实上和循环是等价的，没有循环语句的编程语言只能通过尾递归实现循环。
  • 3. Python标准的解释器没有针对尾递归做优化，任何递归函数都存在栈溢出的问题。