Python recursion with dictionary?

Question

I have a recursion function defined as follows:

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

and if I run it with the following parameters:

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

I get this 13, but I expected the sum to be 8? Since the recursion would look something like this:

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

which equals = 2 + 2 + 2 + 2 = 8? Could someone explain? Thank you!

just put a print statement as your first statement, to log your input parameters... And everything will become clear ;-p — Leo
– Leo, Commented Oct 19, 2020 at 8:11

khelwood · Accepted Answer · 2020-10-19 08:22:15Z

3

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

or if you prefer:

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

This is the Fibonacci sequence.

edited Oct 19, 2020 at 8:22

answered Oct 19, 2020 at 8:12

khelwood

59.7k14 gold badges91 silver badges116 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Zopui · Accepted Answer · 2020-10-19 12:37:42Z

1

You are picturing your recursion falsely. It looks like this:

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

edited Oct 19, 2020 at 12:37

answered Oct 19, 2020 at 8:15

Zopui

411 silver badge4 bronze badges

Collectives™ on Stack Overflow

Python recursion with dictionary?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related