斐波那契求和与记忆[重复]

Question

这个问题在这里已经有了答案:

斐波那契偶数之和 < X (5个答案)

封闭 上月.

我正在学习一门编程课程，有一个关于fibonacci sums和递归的问题.规则如下。

写一个函数fibsum(N) 返回所有小于N的偶数斐波那契项的和。

我想我已经很接近了，但是我的求和并没有正常工作，另外我还希望函数能工作得很高（比如N=10**6至少），这是我目前的代码。

def fibsum(n, memo = {}):

added = 0

if n<0:
    return 0

if n== 1 or n == 0:
    return 1

else:
    if (n-1) in memo.keys():
        f1 = memo[n-1]
    else:
        memo[n-1] = fibsum(n-1)
        f1 = memo[n-1]

    if (n-2) in memo.keys():
        f2 = memo[n-2]
    else:
        memo[n-2] = fibsum(n-2)
        f2 = memo[n-2]

    if f1+f2 < 44:
        if (f1+f2) % 2 == 0:
            added += f1+f2
            print ("look here",added)
            return added 

    print (f1+f2)   
    return f1 + f2          

我留下了一些打印语句，因为我想调试这个问题，但我没有运气。

编辑：我已经被链接到另一个问题，但在这种情况下，它是迭代完成的，如果可能的话，我想以递归方式进行

Answer 1

memoization对fib的大值没有帮助

但作为一个旁观者，分开你的逻辑。

def fib(n):
    """
     simple recursive fibonacci function
    """
    if n == 0:
       return 1
    return n + fib(n-1)

然后做一个通用的备忘录装饰器

def memoize(fn):
    cache = {}
    def _tokenize(*args,**kwargs):
        return str(args)+str(kwargs)
    def __inner(*args,**kwargs):
        token = _tokenize(*args,**kwargs)
        if token not in cache:
           cache[token] = fn(*args,**kwargs)
        return cache[token]

现在只要装饰一下你的简单递归函数就可以了

@memoize
def fib(n):
    """
     simple recursive fibonacci function
    """
    if n == 0:
       return 1
    return n + fib(n-1)

现在你可以使你的fibsum方法（也可以记忆它）。

@memoize
def get_fib_nums(n):
    if n == 0:
       return [1]
    return [n] + get_fib_nums(n)



@memoize
def fibevensum(n):
    return sum(n for n in get_fib_nums(n) if n%2 == 0)