#!usr/bin/env python  
#encoding:utf-8    
''''''' 
__Author__:沂水寒城 
功能：尾递归 
'''   
import time 
def Fib_recursion(num): 
  ''''' 
  直接使用递归法求解斐波那契数量的第num个数字 
  ''' 
  if num<2: 
   return num  
  return Fib_recursion(num-1)+Fib_recursion(num-2) 
 
def Fib_tail_recursion(num,res,temp): 
  ''''' 
  使用尾递归法求解斐波那契数量的第num个数字 
  ''' 
  if num==0: 
    return res  
  else: 
    return Fib_tail_recursion(num-1, temp, res+temp)  
def Fib_circle(num): 
  ''''' 
  直接使用循环来求解 
  ''' 
  a=0 
  b=1 
  for i in range(1,num): 
    c=a+b 
    a=b 
    b=c  
  return c  
  
if __name__ == '__main__': 
  num_list=[5,10,20,30,40,50] 
  for num in num_list: 
    start_time=time.time() 
    print Fib_recursion(num) 
    end_time=time.time() 
    print Fib_tail_recursion(num,0,1) 
    end_time2=time.time() 
    print Fib_circle(num) 
    end_time3=time.time() 
    print '正在求解的斐波那契数字下标为%s' %num 
    print '直接递归耗时为 ：', end_time-start_time 
    print '尾递归调用耗时为：', end_time2-end_time 
    print '直接使用循环耗时为：', end_time3-end_time2 

5 
5 
5 
正在求解的斐波那契数字下标为5 
直接递归耗时为 ： 6.38961791992e-05 
尾递归调用耗时为： 2.31266021729e-05 
直接使用循环耗时为： 1.97887420654e-05 
55 
55 
55 
正在求解的斐波那契数字下标为10 
直接递归耗时为 ： 6.60419464111e-05 
尾递归调用耗时为： 3.31401824951e-05 
直接使用循环耗时为： 1.8835067749e-05 
6765 
6765 
6765 
正在求解的斐波那契数字下标为20 
直接递归耗时为 ： 0.00564002990723 
尾递归调用耗时为： 3.09944152832e-05 
直接使用循环耗时为： 2.09808349609e-05 
832040 
832040 
832040 
正在求解的斐波那契数字下标为30 
直接递归耗时为 ： 0.39971113205 
尾递归调用耗时为： 1.69277191162e-05 
直接使用循环耗时为： 1.19209289551e-05 
102334155 
102334155 
102334155 
正在求解的斐波那契数字下标为40 
直接递归耗时为 ： 39.0365440845 
尾递归调用耗时为： 2.19345092773e-05 
直接使用循环耗时为： 1.78813934326e-05 
12586269025 
12586269025 
12586269025 
正在求解的斐波那契数字下标为50 
直接递归耗时为 ： 4915.68643498 
尾递归调用耗时为： 2.19345092773e-05 
直接使用循环耗时为： 2.09808349609e-05