使用内存vs循环的递归
使用内存vs循环的递归
提问于 2020-08-03 18:30:48
我做了两个函数来计算斐波那契数列，一个使用带记忆的递归，另一个使用循环；
def fib_rec(n, dic = {0 : 0, 1 : 1}):
if n in dic:
return dic[n]
else:
fib = fib_rec(n - 2, dic) + fib_rec(n - 1, dic)
dic[n] = fib
return fibdef fib_loop(n):
if n == 0 or n == 1:
return n
else:
smaller = 0
larger = 1
for i in range(1, n):
smaller, larger = larger, smaller + larger
return larger我听说斐波那契数列经常使用递归来求解，但我想知道为什么。我的两个算法都是线性时间复杂度的，但是使用循环的算法不需要携带所有过去斐波那契数的字典，也不会超过Python的递归深度。
这个问题是用递归来解决的，还是我漏掉了什么？
回答 1
Stack Overflow用户
发布于 2020-08-03 20:14:08
通常的递归O(N) Fibonacci实现更像这样：
def fib(n, a=0, b=1):
if n == 0: return a
if n == 1: return b
return fib(n - 1, b, a + b)这种方法的优点(除了它使用O(1)内存的事实之外)是尾递归的:一些编译器和/或运行时可以利用这一点将其秘密地转换为简单的跳转指令。这称为尾部调用优化。
不幸的是，Python没有使用这种策略，所以它将为调用堆栈使用额外的内存，正如您所提到的，这很快就会达到Python的递归深度限制。
Fibonacci序列主要是一个玩具问题，用来教人们如何编写算法和关于大的哦符号。它有优雅的函数解决方案以及动态编程的优势(基本上是基于字典的解决方案)，但它实际上也是一个已解决的问题。
我们也可以走得更快。页面https://www.nayuki.io/page/fast-fibonacci-algorithms描述了如何实现。它包括一个用Python编写的快速加倍算法，我想在这里包含它，但遗憾的是，许可证不允许我这样做。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/63227792
复制相关文章
相似问题
腾讯云开发者
