Блог

Главная - Вопросы по программированию - Рекурсия Python со словарем?

Рекурсия Python со словарем?

#python #recursion

#python #рекурсия

Вопрос:

У меня есть функция рекурсии, определенная следующим образом:

 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? Может кто-нибудь объяснить? Спасибо!

Комментарии:

1. просто поместите оператор print в качестве первого оператора, чтобы зарегистрировать входные параметры… И все станет ясно;-p

Ответ №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))   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

Это последовательность Фибоначчи.

Ответ №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)               2
myfunc(2, d)   myfunc(1, d)     2   2   1   2   1   2
2   1   2   2   1   2   1   2
which is 13