На этом шаге мы рассмотрим этот вариант рекурсии.
Приведенная на предыдущем шаге формула для определения числа в последовательности Фибоначчи (рисунок 1) представляет собой псевдокод, который можно легко перевести в рекурсивную функцию Python. (Рекурсивная функция - это функция, которая вызывает сама себя.)
Рис.1. Рост каждого человечка равен сумме роста двух предыдущих
Такой механический перевод станет нашей первой попыткой написать функцию, возвращающую заданное значение последовательности Фибоначчи.
def fib1(n: int) -> int: return fib(n - 1) + fib(n - 2) if __name__ == "__main__": print(fib1(5))
Попробуем запустить эту функцию, вызвав ее и передав ей значение 5.
Ой-ой-ой! При попытке запустить программу получаем ошибку превышения максимальной глубины рекурсии:
RecursionError: maximum recursion depth exceeded
Рис.2. Результат работы приложения
Проблема в том, что функция fib1() будет работать вечно, не возвращая окончательный результат. Каждый вызов fib1() приводит к двум другим вызовам fib1(), и так без конца. Такую ситуацию называют бесконечной рекурсией (рисунок 3), она подобна бесконечному циклу.
Рис.3. Рекурсивная функция fib(n) вызывает сама себя с аргументами n - 2 и n - 1
На следующем шаге мы рассмотрим использование базовых случаев.
