Рекурсия – это когда функция вызывает саму себя. Логика рекурсивной функции, как правило, состоит из двух ветвей.

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

Короткая ветвь определяет критерий выхода из рекурсии.

Oct. 12, 2023, Источник

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

deffactorial(n):
# терминальное условие, которое остановит рекурсию
	if n<= 0:
	return 1
# рекурсивный вызов
return n* factorial(n- 1)

factorial(5)
# 120
# тоже самое, что 5 * 4 * 3 * 2 * 1

 

Oct. 12, 2023, Источник

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

Принцип работы

Состоит из двух частей:

1. Базовый случай: Условие, при котором рекурсия прекращается, чтобы избежать бесконечного цикла вызовов.
2. Рекурсивный случай: Вызов функции самой себей с измененными параметрами.

Пример:

Простым примером может служить функция вычисления факториала числа `n`, где факториал `n` (обозначается как `n!`) — это произведение всех натуральных чисел от 1 до `n`.

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

В этом примере, если `n` не равно 1, функция вызывает сама себя с параметром `n-1`. Эти вызовы продолжаются, пока `n` не достигнет 1, после чего вызовы начинают возвращаться обратно, последовательно умножая числа.

Преимущества и недостатки

Преимущества:

• Упрощает решение сложных задач, разбивая их на более мелкие.
• Облегчает чтение и понимание кода при решении определенных типов задач.

Недостатки:

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

Рекурсия — это ключевой концепт, позволяющий решать задачи, которые сложно или неудобно решать итеративными методами. Правильное использование рекурсии требует понимания её принципов работы и умения определять базовые случаи для предотвращения бесконечных вызовов.

Feb. 22, 2024, easyoffer