python 2.7 - 递归斐波那契爆炸

我有两个函数fib1和fib2来计算斐波纳契。python 2.7 - 递归斐波那契爆炸

def fib1(n): 
    if n < 2: 
     return 1 
    else: 
     return fib1(n-1) + fib1(n-2) 

def fib2(n): 
    def fib2h(s, c, n): 
     if n < 1: 
      return s 
     else: 
      return fib2h(c, s + c, n-1) 
    return fib2h(1, 1, n)

fib2直到它炸毁递归限制正常工作。如果理解正确，Python不会针对尾递归进行优化。这对我来说很好。

什么让我是fib1开始放缓，即使值很小的n也停下来。为什么会发生？在它迟缓之前它怎么没有达到递归限制？

来源

2012-10-10 JBoyer

CPU时间：用户0.35 S，SYS：0.00 s，共0.35小号墙时间：0.35小号......这就是花了多长时间我要'FIB1（30）'..似乎理由在Python 3中能够使用 –

'fib2（30）'，real：0m0.032s，user：0m0.025s，sys：0m0.006s。您使用的是什么版本的Python？ –

@JoranBeasley尝试fib1（100） – JBoyer

基本上，你是在浪费大量的时间。你可以很容易地记忆这样的功能

def fib1(n, memo={}): 
    if n in memo: 
     return memo[n] 
    if n < 2: 
     memo[n] = 1 
    else: 
     memo[n] = fib1(n-1) + fib1(n-2) 
    return memo[n]

你会注意到我使用了一个空字典作为默认参数。这通常是一个坏主意，因为每个函数调用都使用相同的字典作为缺省值。

在这里，我趁着通过使用它来memoize的每个结果我计算

你也可以主要用0和1的备忘录，以避免需要的n < 2测试

def fib1(n, memo={0: 1, 1: 1}): 
    if n in memo: 
     return memo[n] 
    else: 
     memo[n] = fib1(n-1) + fib1(n-2) 
    return memo[n]

这成为

def fib1(n, memo={0: 1, 1: 1}): 
    return memo.setdefault(n, memo.get(n) or fib1(n-1) + fib1(n-2))

来源

2012-10-11 00:28:45

+1教我一些新东西今天通过实际利用有一个默认参数在多个调用中引用相同的对象。 –

这是非常聪明的 – JBoyer

后来的版本会导致'n <0'的无限递归，不过不可否认的是，它不在问题域内。 –

想想每个中的递归树。第二个版本是递归的一个分支，在函数调用的参数计算中增加了它，然后它返回值。如您所知，Python不需要尾递归优化，但是如果尾调用优化是解释器的一部分，尾递归优化也可以被触发。

另一方面，第一个版本需要2个递归分支在每个级别！因此，相当多的函数skyrockets可能执行。不仅如此，大部分工作都重复了两次！考虑：fib1(n-1)最终再次调用fib1(n-1)，这与从第一个调用帧的参考点调用fib1(n-2)相同。但在计算出该值后，必须再次将它加到fib1(n-2)的值上！所以这项工作被不必要地重复了很多次。

来源

2012-10-11 00:09:48

你的问题不是python，它是你的算法。 fib1就是tree recursion的一个很好的例子。你可以找到一个证明here on stackoverflow，这个特定的算法是（〜θ(1.6ⁿ)）。

n=30（显然来自评论）大约需要三分之一秒。如果计算时间大大加快了为1.6^n，我们预计n=100通过计算一遍又一遍n的值相同的FIB1约需2.1 million years.

来源

2012-10-11 00:12:55

不错:)我喜欢你对n = 100会花费多少时间的解释:) ...时间可以获得大约210万个核心......然后你可以在一年内完成：P –

python 2.7 - 递归斐波那契爆炸

回答

相关问题