Рекурсивные функции в Python

Введение

Добро пожаловать в мистическую страну Пифонезии, великоеmpire, славящееся продвинутым использованием магических и математических конструкций. В качестве главного королевского гвардейца страны вас назначили защитником самого ценного артефакта империи: Рекурсивного Кристала. Легенды утверждают, что он был создан с использованием древнего кода, который зацикливается внутри себя, создавая бесконечный источник энергии. Чтобы лучше понять и защитить этот артефакт, вы должны овладеть искусством рекурсии в Python - именно навык, который был использован для его создания.

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

Введение в рекурсию

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

Давайте начнем с создания простой рекурсивной функции, которая вычисляет факториал числа. Факториал числа n - это произведение всех положительных целых чисел, меньших или равных n.

Откройте ~/project/factorial.py в своем любимом текстовом редакторе и добавьте следующий код:

def factorial(n):
    if n == 0:  ## Базовый случай
        return 1
    else:        ## Рекурсивный случай
        return n * factorial(n - 1)

## Пример использования
print(factorial(5))

Для запуска кода используйте следующую команду:

python3 factorial.py

Ожидаемый результат должен быть 120, так как 5! = 5 * 4 * 3 * 2 * 1 = 120.

Рекурсия с несколькими базовыми случаями

Далее вы узнаете, как построить рекурсивную функцию с несколькими базовыми случаями. Создадим функцию fibonacci в файле fibonacci.py, которая вычислит последовательность Фибоначчи до n-го числа. Последовательность Фибоначчи - это ряд чисел, где каждое число равно сумме двух предыдущих, начиная с 0 и 1.

Введите следующий код в ~/project/fibonacci.py:

def fibonacci(n):
    if n == 0:  ## Первый базовый случай
        return 0
    elif n == 1:  ## Второй базовый случай
        return 1
    else:         ## Рекурсивный случай
        return fibonacci(n - 1) + fibonacci(n - 2)

## Пример использования
print(fibonacci(10))

Запустите код командой:

python3 fibonacci.py

Ожидаемый вывод должен быть 55, так как это 10-е число в последовательности Фибоначчи.

Резюме

В этом практическом занятии мы углубились в концепцию рекурсии в Python, приложив ее к двум различным математическим последовательностям. Процесс проектирования был основан на создании интересной сюжетной линии, которая делает обучение рекурсии интересным и актуальным. Задачи были структурированы от более простого случая с одним базовым случаем - факториала, до более сложной ситуации с несколькими базовыми случаями в последовательности Фибоначчи, чтобы обеспечить всестороннее понимание.

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