python裝飾器與遞歸算法詳解

1、python裝飾器

剛剛接觸python的裝飾器，簡直懵逼了，直接不懂什么意思啊有木有，自己都忘了走了多少遍Debug，查了多少遍資料，猜有點(diǎn)點(diǎn)開始明白了?？偨Y(jié)了一下解釋得比較好的，通俗易懂的來說明一下：

小P閑來無事，隨便翻看自己以前寫的一些函數(shù)，忽然對(duì)一個(gè)最最最基礎(chǔ)的函數(shù)起了興趣：    
def sum1():
  sum = 1 + 2
  print(sum)
sum1()

此時(shí)小P想看看這個(gè)函數(shù)執(zhí)行用了多長時(shí)間，所以寫了幾句代碼插進(jìn)去了：    
import time
 
def sum1():
  start = time.clock()
  sum = 1+2
  print(sum)
  end = time.clock()
  print("time used:",end - start)
 
sum1()

運(yùn)行之后，完美~~

可是隨著繼續(xù)翻看，小P對(duì)越來越多的函數(shù)感興趣了，都想看下他們的運(yùn)行時(shí)間如何，難道要一個(gè)一個(gè)的去改函數(shù)嗎？當(dāng)然不是！我們可以考慮重新定義一個(gè)函數(shù)timeit，將sum1的引用傳遞給他，然后在timeit中調(diào)用sum1并進(jìn)行計(jì)時(shí)，這樣，我們就達(dá)到了不改動(dòng)sum1定義的目的，而且，不論小P看了多少個(gè)函數(shù)，我們都不用去修改函數(shù)定義了！    
import time
 
def sum1():
  sum = 1+ 2
  print (sum)
 
def timeit(func):
  start = time.clock()
  func()
  end =time.clock()
  print("time used:", end - start)
 
timeit(sum1)

咂一看，沒啥問題，可以運(yùn)行！但是還是修改了一部分代碼，把sum1() 改成了timeit(sum1)。這樣的話，如果sum1在N處都被調(diào)用了，你就不得不去修改這N處的代碼。所以，我們就需要楊sum1()具有和timeit(sum1)一樣的效果，于是將timeit賦值給sum1。可是timeit是有參數(shù)的，所以需要找個(gè)方法去統(tǒng)一參數(shù)，將timeit(sum1)的返回值（計(jì)算運(yùn)行時(shí)間的函數(shù)）賦值給sum1。    
import time
 
def sum1():
  sum = 1+ 2
  print (sum)
 
def timeit(func):
  def test():
    start = time.clock()
    func()
    end =time.clock()
    print("time used:", end - start)
  return test
 
sum1 = timeit(sum1)
sum1()

這樣一個(gè)簡易的裝飾器就做好了，我們只需要在定義sum1以后調(diào)用sum1之前，加上sum1= timeit(sum1)，就可以達(dá)到計(jì)時(shí)的目的，這也就是裝飾器的概念，看起來像是sum1被timeit裝飾了！Python于是提供了一個(gè)語法糖來降低字符輸入量。    
import time
 
def timeit(func):
  def test():
    start = time.clock()
    func()
    end =time.clock()
    print("time used:", end - start)
  return test
 
@timeit
def sum1():
  sum = 1+ 2
  print (sum)
 
sum1()

重點(diǎn)關(guān)注第11行的@timeit，在定義上加上這一行與另外寫sum1 = timeit(sum1)完全等價(jià)。

2、遞歸算法

遞歸算法是一種直接或者間接地調(diào)用自身算法的過程。在計(jì)算機(jī)編寫程序中，遞歸算法對(duì)解決一大類問題是十分有效的，它往往使算法的描述簡潔而且易于理解。

遞歸算法解決問題的特點(diǎn)：
(1) 遞歸就是在過程或函數(shù)里調(diào)用自身。
(2) 在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口。
(3) 遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運(yùn)行效率較低。所以一般不提倡用遞歸算法設(shè)計(jì)程序。
(4) 在遞歸調(diào)用的過程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開辟了棧來存儲(chǔ)。遞歸次數(shù)過多容易造成棧溢出等。所以一般不提倡用遞歸算法設(shè)計(jì)程序。
舉個(gè)栗子：對(duì)一個(gè)數(shù)字進(jìn)行除2求值，直到小于等于1時(shí)退出并輸出結(jié)果    
def divide(n,val):
  n += 1
  print(val)
  if val / 2 > 1:
    aa = divide(n,val/2)
    print('the num is %d,aa is %f' % (n,aa))
  print('the num is %d,val is %f' % (n,val))
  return(val)
 
divide(0,50.0)
結(jié)果說明（不return時(shí)相當(dāng)于嵌套循環(huán)，一層層進(jìn)入在一層層退出）：    
50.0
25.0
12.5
6.25
3.125
1.5625
the num is 6,val is 1.562500
the num is 5,aa is 1.562500
the num is 5,val is 3.125000
the num is 4,aa is 3.125000
the num is 4,val is 6.250000
the num is 3,aa is 6.250000
the num is 3,val is 12.500000
the num is 2,aa is 12.500000
the num is 2,val is 25.000000
the num is 1,aa is 25.000000
the num is 1,val is 50.000000

2、遞歸時(shí)return：    
def divide(n,val):
  n += 1
  print(val)
  if val / 2 > 1:
    aa = divide(n,val/2)
    print('the num is %d,aa is %f' % (n,aa))
    return(aa)
  print('the num is %d,val is %f' % (n,val))
  return(val)
 
divide(0,50.0)

結(jié)果說明（return時(shí)就直接結(jié)束本次操作）：    
50.0
25.0
12.5
6.25
3.125
1.5625
the num is 6,val is 1.562500
the num is 5,aa is 1.562500
the num is 4,aa is 1.562500
the num is 3,aa is 1.562500
the num is 2,aa is 1.562500
the num is 1,aa is 1.562500
用遞歸實(shí)現(xiàn)斐波那契函數(shù)    
def feibo(first,second,stop,list):
 
  if first >= stop or second >= stop:
    return list
  else:
    sum = first + second
    list.append(sum)
    if sum <= stop:
      return feibo(second,sum,stop,list)
 
  return list
 
if __name__ == '__main__':
  first = int(raw_input('please input the first number:'))
  second = int(raw_input('please input the second number:'))
  stop = int(raw_input('please input the stop number:'))
  l = [first,second]
  a = feibo(first,second,stop,l)
  print(a)