递归效率好低啊。如何提高它的效率呢？

wei_Y

1. list1 = []
   
2. list2 = []
   
3. num1 = 1
   
4. def numlist(num):
   
5.     if num == 1 or num ==2:
   
6.         return (1)
   
7.     else:
   
8.         return (numlist(num-1)+numlist(num-2))
   
9. 
   
10. while num1 < 40:
    
11.     num1 +=1
    
12.     list1.append(numlist(num1))
    
13. for i in list1:
    
14.     if i % 2 == 0:
    
15.         list2.append(i)
    
16. print(sum(list2))

复制代码

当把 num1变成40就跑不动了。。

bevin

1. list1 = [0,1,1]
   
2. list2 = []
   
3. ct = 3
   
4. def numlist(num):
   
5.     #global list1
   
6.     res = list1[num-1] + list1[num-2]
   
7.     list1.append(res)
   
8.     return res
   
9. 
   
10. while ct < 40:
    
11.     numlist(ct)
    
12.     ct += 1
    
13. 
    
14. list2 = filter(lambda x: x%2 == 0,list1[1:])
    
15. print sum(list2)
    
16. 
    
17. #print sum(filter(lambda x: x%2 == 0,list1[1:]))
    

复制代码

这是2.x的运行代码，做了一些改进(filter，lambda函数的使用，列表解析等)
这里可以直接取list1之前计算的结果。或者使用for语句来计算。。。能不使用递归就尽量不要用递归哦

bevin

1. def numlist(num):
   
2.     tlist = [1,1]
   
3.     for i in range(2,num):
   
4.         tlist.append(tlist[i-1]+tlist[i-2])
   
5.     return tlist[-1]
   
6. 
   
7. print [numlist(x) for x in range(1,40)]
   

复制代码

这是for语句的实现，要比上面慢点，但是比递归快多了

wei_Y

bevin 发表于 2014-9-6 11:14
这是for语句的实现，要比上面慢点，但是比递归快多了

嗯。我开始输入的4000，跑了很长时间没有结果，我又换成400，还是没结果，换成40，跑了好久才有的结果。。递归效率真的太差了。。

墨白_找

学习~

破渔网兜兜

学习了~~~

骑猪撞宝马

  来学习的。

骑猪撞宝马

  来学习啦，多多指教

川本姨夫

不知道Python支持尾递归优化不，一般的线性递归或树形递归效率都是很低的。  

wei_Y

川本姨夫 发表于 2014-9-12 15:06
不知道Python支持尾递归优化不，一般的线性递归或树形递归效率都是很低的。

请教一下什么叫尾递归优化。。