В любой рекурсивной функции обязательно должны быть два основных компонента:
Базовый случай (условие выхода) – предотвращает бесконечную рекурсию.
Рекурсивный случай – уменьшает задачу и приближает её к базовому случаю.
🚩Базовый случай (условие выхода)
Это условие, при котором рекурсия заканчивается и начинается возврат значений вверх по стеку вызовов.
Без него рекурсия уйдёт в бесконечный цикл и вызовет
RecursionError. def factorial(n):
if n == 0: # Базовый случай
return 1
return n * factorial(n - 1) # Рекурсивный случай
print(factorial(5)) # 120
🚩Рекурсивный случай
Это часть функции, которая уменьшает входные данные и вызывает саму себя.
Без уменьшения данных функция никогда не достигнет базового случая.
Пример: сумма чисел от
n до 1 def sum_numbers(n):
if n == 1: # Базовый случай
return 1
return n + sum_numbers(n - 1) # Рекурсивный случай
print(sum_numbers(5)) # 15 (5+4+3+2+1)
🚩Ошибки при рекурсии
Нет базового случа*
def infinite_recursion(n):
print(n)
return infinite_recursion(n - 1) # Нет выхода!
# infinite_recursion(5) # Вызовет RecursionError!
Неправильное уменьшение аргумента
def incorrect_recursion(n):
if n == 0:
return 1
return n * incorrect_recursion(n + 1) # Увеличение вместо уменьшения!
# incorrect_recursion(5) # Бесконечная рекурсия
Ставь 👍 и забирай 📚 Базу знаний