На этом шаге мы рассмотрим назначение и использование таких случаев.
Обратите внимание: до тех пор пока мы не запустили fib1(), среда Python никак не сообщает о том, что с функцией что-то не так. Избегать бесконечной рекурсии - обязанность программиста, а не компилятора или интерпретатора. Причина бесконечной рекурсии заключается в том, что мы нигде не указали базовый случай. В рекурсивной функции базовый случай служит точкой остановки.
Естественные базовые случаи для функции Фибоначчи - это два первых специальных значения последовательности - 0 и 1. Ни 0, ни 1 не являются суммой двух предыдущих чисел последовательности. Это два первых специальных значения. Давайте попробуем указать их в качестве базовых случаев.
def fib2(n: int) -> int: if n < 2: # базовый случай return n return fib2(n - 2) + fib2(n - 1) # рекурсивный случай if __name__ == "__main__": print(fib2(5)) print(fib2(10))
В отличие от первоначального предложения версия fib2() функции Фибоначчи возвращает 0 для аргумента, равного нулю (fib2(0)), а не единице.
В контексте программирования это имеет смысл, поскольку мы привыкли к последовательностям, начинающимся с нулевого элемента.
Функция fib2() может быть успешно вызвана и возвращает правильные результаты. Попробуйте вызвать ее для нескольких небольших значений 5 и 10.
5
55
He пытайтесь вызывать fib2(50). Это никогда не закончится! Почему? Потому что каждый вызов fib2() приводит к двум новым вызовам fib2() - рекурсивным вызовам fib2(n - l) и fib2(n - 2) (рисунок 1).
Рис.1. Каждый вызов fib2(), не являющийся базовым случаем, приводит к еще двум вызовам fib2()
Другими словами, дерево вызовов растет в геометрической прогрессии. Например, вызов fib2(4) приводит к такой последовательности вызовов:
fib2(4) -> fib2(3), fib2(2) fib2(3) -> fib2(2), fib2(1) fib2(2) -> fib2(1), fib2(0) fib2(2) -> fib2(1), fib2(0) fib2(1) -> 1 fib2(1) -> 1 fib2(1) -> 1 fib2(0) -> 0 fib2(0) -> 0
Если посчитать их (и проследить, добавив несколько вызовов print), то обнаружится, что для вычисления всего лишь четвертого элемента нужны девять вызовов fib2()! Дальше - хуже. Для вычисления пятого элемента требуется 15 вызовов, десятого - 177, двадцатого - 21 891. Мы могли бы написать и что-нибудь получше.
На следующем шаге мы рассмотрим мемоизацию.
