[已解决]迭代与递归运行速度不同的原因？

幻影骑士

迭代斐波那契数列

def fab(n):
    n1 = 1
    n2 = 1
    n3 = 1
#先默认n3的初始值为 1
    if n < 1:
        print('输入有误！')
        return -1

    while(n-2)>0:
        n3 = n2 + n1
        n1 = n2
        n2 = n3
        n -= 1
# n -= 1--------代表 n = n - 1 ------- 代表循环次数减1
    return n3

result = fab(35)
if result != -1:
    print('总共有%d对小兔子诞生！'%result)


递归斐波那契数列
def fab(n):
    if n < 1:
        print('输入有误！')
        return -1

    if n == 1 or n == 2:
        return 1
    else:
        return fab(n-1) + fab(n-2)

result = fab(35)
if result != 1:
    print('%d 的斐波那契数列是:%d'%(number, result))




问题，为什么，用迭代写的代码跑起来比递归方法写的要快很多？

最佳答案

月排行榜 / 总排行榜

冬雪雪冬

2018-1-10 21:49:08

迭代要一层层的将数据压入堆栈，再逆向逐级返回，占用大量内存，效率上比递归要低很多。

跳转到最佳答案楼层

冬雪雪冬

迭代要一层层的将数据压入堆栈，再逆向逐级返回，占用大量内存，效率上比递归要低很多。

影-死神

可能是因为递归占用内存更多吧，计算起来，要挂起很多程序
而迭代就是正常的运行，只有一个在跑，肯定快些

幻影骑士

冬雪雪冬 发表于 2018-1-10 21:49
迭代要一层层的将数据压入堆栈，再逆向逐级返回，占用大量内存，效率上比递归要低很多。

非常专业，谢谢

幻影骑士

影-死神 发表于 2018-1-10 21:49
可能是因为递归占用内存更多吧，计算起来，要挂起很多程序
而迭代就是正常的运行，只有一个在跑，肯定快些

通俗易懂，深入浅出，感谢