Python递归与字典？

Question

我有一个递归函数，定义如下：

def myfunc(n, d):
    if n in d:
        return d[n]
    else:
        return myfunc(n-1,d) + myfunc(n-2,d)

如果我使用以下参数运行它：

myfunc(6, {1:1,2:2})

我得到13，但我想总数是8？因为递归看起来像这样：

myfunc(5,d) + myfunc(4,d)
myfunc(4,d) + 2
myfunc(3,d) + 2
2 + 2

哪个等于2+2+2+2=8？有人能解释一下吗？谢谢大家!

Answer 1

你在错误地描绘你的递归。看起来是这样的：

myfunc(6, d)
myfunc(5, d) + myfunc(4, d)
myfunc(4, d) + myfunc(3, d)   +    myfunc(3, d) + myfunc(2, d)
myfunc(3, d) + myfunc(2, d)   +    myfunc(2, d) + myfunc(1, d)    +   myfunc(2, d) + myfunc(1, d)        +      2
myfunc(2, d) + myfunc(1, d)   + 2 + 2 + 1 + 2 + 1 + 2
2 + 1 + 2 + 2 + 1 + 2 + 1 + 2
which is 13

Answer 2

myfunc(6,d) == myfunc(5,d) + myfunc(4,d)
            == myfunc(4,d) + myfunc(3,d) + myfunc(3,d) + myfunc(2,d)
            == (myfunc(3,d) + myfunc(2,d)) + (myfunc(2,d) + myfunc(1,d)) + (myfunc(2,d) + myfunc(1,d)) + myfunc(2,d)
            == ((myfunc(2,d) + myfunc(1,d)) + myfunc(2,d)) + (myfunc(2,d) + myfunc(1,d)) + (myfunc(2,d) + myfunc(1,d)) + myfunc(2,d)
            == 2 + 1 + 2 + 2 + 1 + 2 + 1 + 2
            == 13

或者，如果您愿意：

myfunc(1,d) == 1
myfunc(2,d) == 2
myfunc(3,d) == myfunc(2,d) + myfunc(1,d) == 2 + 1 == 3
myfunc(4,d) == myfunc(3,d) + myfunc(2,d) == 3 + 2 == 5
myfunc(5,d) == myfunc(4,d) + myfunc(3,d) == 5 + 3 == 8
myfunc(6,d) == myfunc(5,d) + myfunc(4,d) == 8 + 5 == 13

这是Fibonacci sequence