На этом шаге мы рассмотрим итерационный способ вычисления функции Фибоначчи.
Существует еще более быстрый вариант. Мы можем решить задачу Фибоначчи старым добрым итеративным методом.
def fib5(n: int) -> int: if n == 0: return n # специальный случай last: int = 0 # начальное значение fib(0) next: int = 1 # начальное значение fib(l) for _ in range(1, n): last, next = next, last + next return next if __name__ == "__main__": print(fib5(5)) print(fib5(50))
В теле цикла for в fib5() используется распаковка кортежа - возможно, слишком хитроумным способом. Кому-то может показаться, что это сделано для краткости в ущерб
удобочитаемости. Другие полагают, что краткость сама по себе улучшает удобство чтения. Суть в том, что переменной last присваивается предыдущее значение next, a next - предыдущее
значение last плюс предыдущее значение next. Это позволяет избежать создания временной переменной для хранения старого значения next после изменения last, но
перед изменением next. Такое применение распаковки кортежа для определенных переменных широко распространено в Python.
При таком подходе тело цикла for будет выполняться максимум n - 1 раз. Другими словами, это самая эффективная версия. Сравните 19 проходов тела цикла for с 21891 рекурсивным вызовом fib2() для 20-го числа Фибоначчи. В реальных приложениях это может серьезно изменить ситуацию!
В рекурсивных решениях мы приступали к задаче с конца. В этом итеративном решении начинаем с начала. Иногда рекурсия является наиболее интуитивно понятным способом решения задачи. Например, суть функций fib1() и fib2() - это, в сущности, просто механический перевод исходной формулы Фибоначчи. Однако наивные рекурсивные решения могут значительно ухудшить производительность. Помните, что любую задачу, которая может быть решена рекурсивно, можно решить и итеративным способом.
На следующем шаге мы рассмотрим генерацию чисел Фибоначчи.
