8.python lambda和遞歸函數(shù)

一、lambda函數(shù)

lambda 函數(shù)是一種快速定義單行的最小函數(shù)，是從 Lisp 借用來的，可以用在任何需要函數(shù)的地方 。

  • 1. 下面的例子比較了傳統(tǒng)的函數(shù)定義def與lambda定義方式：
>>> def f ( x ,y):
...   return x * y
...
>>> f ( 2,3 )
6
>>> g = lambda x ,y: x * y
>>> g ( 2,3 )
6

可以看到，兩個函數(shù)得到的結(jié)果一樣，而對于實(shí)現(xiàn)簡單功能的函數(shù)來說，使用lambda函數(shù)來定義更加精簡靈活，還可以直接把函數(shù)賦值給一個變量，用變量名來表示函數(shù)名。
其實(shí)lambda函數(shù)在很多時候都是不需要賦值給一個變量的。

  • 2. 使用lambda函數(shù)還有一些注意事項(xiàng)：
      1. lambda 函數(shù)可以接收任意多個參數(shù) (包括可選參數(shù)) 并且返回單個表達(dá)式的值。
      1. lambda 函數(shù)不能包含命令，包含的表達(dá)式不能超過一個。
      1. lambda語句用來創(chuàng)建函數(shù)對象。本質(zhì)上，lambda需要一個參數(shù)，后面僅跟單個表達(dá)式作為函數(shù)體，而表達(dá)式的值被這個新建的函數(shù)返回。注意，即便是print語句也不能用在 lambda形式中，只能使用表達(dá)式。
  • 3. def 與lambda的區(qū)別
      1. lambda是在python中使用lambda來創(chuàng)建匿名函數(shù)，而用def創(chuàng)建的方法是有名稱的。
      1. lambda會創(chuàng)建一個函數(shù)對象，但不會把這個函數(shù)對象賦給一個標(biāo)識符，而def則會把函數(shù)對象賦值給一個變量。
      1. lambda它只是一個表達(dá)式，而def則是一個語句。因?yàn)閐ef是語句，不是表達(dá)式不能嵌套在里面，lambda表達(dá)式在“：”后只能有一個表達(dá)式。也就是說，在def中，用return可以返回的也可以放在lambda后面，不能用return返回的也不能定義在python lambda后面。因此，像if或for或print這種語句就不能用于lambda中，lambda一般只用來定義簡單的函數(shù)。
  • 4.實(shí)例
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 ()

二、遞歸函數(shù)

  • 1. 定義
    在函數(shù)內(nèi)部，可以調(diào)用其他函數(shù)。如果一個函數(shù)在內(nèi)部調(diào)用自身本身，這個函數(shù)就是遞歸函數(shù)。

  • 2. 遞歸特性

    1. 記住所有的遞歸函數(shù)都有一個退出條件
    2. 相鄰兩次重復(fù)之間有緊密的聯(lián)系，前一次要為后一次做準(zhǔn)備（通常前一次的輸出就作為后一次的輸入）。
    3. 遞歸效率不高，遞歸層次過多會導(dǎo)致棧溢出（在計(jì)算機(jī)中，函數(shù)調(diào)用是通過棧（stack）這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的，每當(dāng)進(jìn)入一個函數(shù)調(diào)用，棧就會加一層棧幀，每當(dāng)函數(shù)返回，棧就會減一層棧幀。由于棧的大小不是無限的，所以，遞歸調(diào)用的次數(shù)過多，會導(dǎo)致棧溢出）
    4. 遞歸的層數(shù)在python里是有限制的 997/998層，可以使用sys模塊對遞歸層數(shù)進(jìn)行修改sys.setrecursionlimit(10000000)。

  • 3. 實(shí)例詳解

      1. 計(jì)算階乘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)

如果我們計(jì)算fact(5)，可以根據(jù)函數(shù)定義看到計(jì)算過程如下：

===> 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

遞歸函數(shù)的優(yōu)點(diǎn)是定義簡單，邏輯清晰。理論上，所有的遞歸函數(shù)都可以寫成循環(huán)的方式，但循環(huán)的邏輯不如遞歸清晰。
使用遞歸函數(shù)需要注意防止棧溢出。在計(jì)算機(jī)中，函數(shù)調(diào)用是通過棧（stack）這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的，每當(dāng)進(jìn)入一個函數(shù)調(diào)用，棧就會加一層棧幀，每當(dāng)函數(shù)返回，棧就會減一層棧幀。由于棧的大小不是無限的，所以，遞歸調(diào)用的次數(shù)過多，會導(dǎo)致棧溢出。可以試試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

解決遞歸調(diào)用棧溢出的方法是通過尾遞歸優(yōu)化，事實(shí)上尾遞歸和循環(huán)的效果是一樣的，所以，把循環(huán)看成是一種特殊的尾遞歸函數(shù)也是可以的。

尾遞歸是指，在函數(shù)返回的時候，調(diào)用自身本身，并且，return語句不能包含表達(dá)式。這樣，編譯器或者解釋器就可以把尾遞歸做優(yōu)化，使遞歸本身無論調(diào)用多少次，都只占用一個棧幀，不會出現(xiàn)棧溢出的情況。

上面的fact(n)函數(shù)由于return n * fact(n - 1)引入了乘法表達(dá)式，所以就不是尾遞歸了。要改成尾遞歸方式，需要多一點(diǎn)代碼，主要是要把每一步的乘積傳入到遞歸函數(shù)中：

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)僅返回遞歸函數(shù)本身，product * count和count + 1在函數(shù)調(diào)用前就會被計(jì)算，不影響函數(shù)調(diào)用。
fact(5)對應(yīng)的fact_iter(1, 1, 5)的調(diào)用如下：

===> 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

尾遞歸調(diào)用時，如果做了優(yōu)化，棧不會增長，因此，無論多少次調(diào)用也不會導(dǎo)致棧溢出。

遺憾的是，大多數(shù)編程語言沒有針對尾遞歸做優(yōu)化，Python解釋器也沒有做優(yōu)化，所以，即使把上面的fact(n)函數(shù)改成尾遞歸方式，也會導(dǎo)致棧溢出。

有一個針對尾遞歸優(yōu)化的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?，F(xiàn)在，只需要使用這個@tail_call_optimized，就可以順利計(jì)算出fact(1000)：

>>> fact(1000)
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
  • 4. 總結(jié)
      1. 使用遞歸函數(shù)的優(yōu)點(diǎn)是邏輯簡單清晰，缺點(diǎn)是過深的調(diào)用會導(dǎo)致棧溢出。
      1. 針對尾遞歸優(yōu)化的語言可以通過尾遞歸防止棧溢出。尾遞歸事實(shí)上和循環(huán)是等價的，沒有循環(huán)語句的編程語言只能通過尾遞歸實(shí)現(xiàn)循環(huán)。
      1. Python標(biāo)準(zhǔn)的解釋器沒有針對尾遞歸做優(yōu)化，任何遞歸函數(shù)都存在棧溢出的問題。
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容