Как заставить рекурсивную фиб-функцию возвращать правильное значение с памяткой

Question

Я изучаю запоминание в рекурсивных функциях и наткнулся на пример Фибоначчи на Youtube. Я никогда не видел, чтобы человек запускал код, поэтому, возможно, он написал его неправильно.

Когда я скопировал код и попытался запустить его, я сначала получил ошибку, так как я объявил memo без диапазона, поэтому я просто установил диапазон на вход + 1 (так как я не использую 0-индекс) и, таким образом, решил эту проблему. Но теперь я застрял в неправильном возвращаемом значении.

def fib(num, memo=[]):
    if num == 0:
        return 0
    elif num == 1 or num == 2:
        return 1
    elif memo[num] != None:
        return memo[num]
    else:
        memo[num] = fib(num-1, memo) + fib(num-2, memo)
        return memo[num]

uInput = int(input("Fibonacci: "))
memo = list(range(uInput + 1))
fibNum = fib(uInput, memo)

print(fibNum)

Приведенный выше код не выдает ошибку, а просто возвращает значение «uInput». Поэтому, если я введу 6 для 6-го числа Фибоначчи, программа вернет 6 вместо 8, что является фактическим 6-м числом. Я не знаю, почему это происходит.

Когда я погуглил проблему, я нашел темы, которые предлагали использовать dicts вместо списков. Все в порядке, если это единственный способ сделать это. Но если есть способ заставить его работать со списком, я бы хотел понять, как это сделать, чтобы понять, почему я столкнулся с этой проблемой.

Answer 1

Доступ к memo[num] никогда не вернется None. Если num выходит за пределы диапазона, IndexError будет повышен. Более того, вы обычно не хотите передавать аргумент memo в вашу функцию и вместо этого позволяете ей полагаться на свой собственный memo объект.

В вашем случае вы хотите проверить, что индекс находится в диапазоне с len. Всякий раз, когда num выходит за пределы диапазона, выходные данные должны вычисляться рекурсивно и запоминаться. Только тогда он может быть возвращен.

def fib(num, memo=[0, 1]):
    if num >= len(memo):
        memo.append(fib(num - 1) +  fib(num - 2))
    return memo[num]

print(fib(10)) # 55

Кстати, вышеприведенное можно легко преобразовать в итеративную функцию, которая обычно более эффективна в Python.

def fib(num, memo=[0, 1]):
    while num >= len(memo):
        memo.append(memo[-1] + memo[-2])
    return memo[num]

Answer 2

Я считаю, что ваш вопрос является отличным аргументом, почему памятку следует применять как декоратор вместо того, чтобы переплетаться с самой функцией:

from functools import lru_cache

@lru_cache()
def fibonacci(number):
    if number == 0:
        return 0

    if number == 1 or number == 2:
        return 1

    return fibonacci(number - 1) + fibonacci(number - 2)

uInput = int(input("Fibonacci: "))

fibNum = fibonacci(uInput)

print(fibNum)

В противном случае вы пытаетесь отладитьдве разные программы одновременно.Попробуйте описанное выше с вводом 100 с декоратором @lru_cache() и без него.

Это, конечно, все еще ограничивается относительно небольшими входами глубиной стека вызовов Python.Существуют итеративные (и даже лучше рекурсивные) алгоритмы, которые могут работать лучше.

Answer 3

Здесь есть ошибка:

memo = list(range(uInput + 1))  # wrong

memo должен содержать None по индексу i для каждого результата fib(i) еще не вычислено:

memo = [None] * (uInput + 1)  # right

Памятка может быть инициализирована в начале последовательности 0,1, что упростит функцию:

def fib(num, memo):
    if memo[num] is None:
       memo[num] = fib(num-1, memo) + fib(num-2, memo)
    return memo[num]

uInput = int(input("Fibonacci: "))
memo = [0,1] + [None]*uInput
fibNum = fib(uInput, memo)

print(fibNum)

Обновление:

В исходном коде есть другая ошибка: memoявляется обязательным аргументом, он не может работать с настройками по умолчанию.

Answer 4

Вы заполнили список memo на list(range(uInput + 1)). Ваша функция затем проверяет memo[num] != None, что должно быть правдой. Таким образом, он всегда делает return memo[num], возвращая число, занесенное в список memo с помощью функции range.

Вы должны удалить эту строку

memo = list(range(uInput + 1))

и передайте первый параметр только при вызове вашей функции.