为什么 Python 不会做很多递归？

Question

我正在做 Project Euler 问题，我排在第二位。问题是：

斐波那契数列中的每一项都是通过添加前两项生成的。从 1 和 2 开始，前 10 项将是： 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 考虑斐波那契数列中不超过四百万的项，求偶数项之和

我正试图在 python 中解决这个问题。我想我有正确的代码，但出于某种原因，当我运行它的 n 大于或等于 27 时，它会等待一分钟，然后 return 0。但是，对于任何事情26 或更低，运行没问题。这是我的代码：

def fib_seq(n):
    if n == 0:
        return n
    elif n == 1:
        return n
    else:
        return fib_seq(n-1) + fib_seq(n-2)

def get_fib_sum(n):
    x = n
    sum = 0
    for i in range(n):
        if fib_seq(x) > 4000000:
            pass
        elif fib_seq(x) % 2 == 0:
            pass
        else:
            sum += fib_seq(x)
            x = i
    return sum

print get_fib_sum(27)

有没有办法解决这个问题，或者至少让它正常工作？如果它有所作为，我正在使用 Wing IDE 101 学生版。

Answer 1

在您的循环中，您使用的是 fib_seq(x)，它应该是 fib_seq(i)

此外，如果你想多减少一点时间，你可以使用记忆技术

def fib_seq(n):
    if n == 0:
        return n
    elif n == 1:
        return n
    else:
        return fib_seq(n-1) + fib_seq(n-2)

def memoize(fn, arg):
 memo = {}
 if arg not in memo:
  memo[arg] = fn(arg)
  return memo[arg]


fibm = memoize(fib_seq,27)
print fibm

Answer 2

为什么要使用递归？您的代码正在一遍又一遍地重新计算 ENTIRE 斐波那契数列...代码只需要偶数项的总和。 NO 不需要递归。在伪代码中：

t1 = 1
t2 = 2;
sum = 2;
do {
   t3 = t1 + t2;
   if (t3 is even) {
      sum += t3;
   }
   t1 = t2;
   t2 = t3;
} while (t2 <= 4000000)

Answer 3

它做了很多递归，这就是为什么要花这么长时间。

get_fib_sum() 将在循环中计算 fib_seq(27) ，这会进行大量递归并需要一段时间。由于 fib_seq(27) 的结果大于 4000000，因此它永远不会向 sum 添加任何内容，最后返回 0。

Answer 4

斐波那契数列经常被用作如何编写递归代码的示例，这很荒谬，因为它有一个非常直接的迭代解决方案：

def fib(n):
    if n < 2:
        return n
    else:
        a, b = 1, 1
        for _ in range(2, n):    # O(n)
            a, b = b, a+b
        return b

不太明显的是它还有一个矩阵表示，

F = [[0, 1]]      # initial state

T = [[0, 1],      # transition matrix
     [1, 1]]

fib(n) = (F * T**n)[0][0]

这非常有用，因为 T**n 可以用 O(log(n)) 步计算。

(顺便说一句，转移矩阵对数的特征向量引出解析解，

phi = (1 + 5**0.5) / 2     # golden ratio
fib(n) = round(phi**n / 5**0.5, 0)

但这不是我要处理的地方。）

看单双产生的项，你看

n:        0,    1,    2,    3,    4,    5,    6,    7,    8, ... 
f(n):     0,    1,    1,    2,    3,    5,    8,   13,   21, ...
e/o:   even,  odd,  odd, even,  odd,  odd, even,  odd,  odd, ...

所以你需要的是 fib(0) + fib(3) + fib(6) + ... 并且计算 T**3 给你直接从一个词到另一个词所需的系数。

剩下的留作 reader 的练习 ;-)

为什么 Python 不会做很多递归？

Why Won't Python Won't Do a Lot of Recursion?

python

recursion

fibonacci