Никак не пойму рекурсию. Объясните на факториале
Читаю про рекурсию третий день, в голове каша. Как функция может вызывать сама себя и не уйти в бесконечность? Желательно на примере факториала.
3 ответа
Рекурсия = база + шаг к базе.
def fact(n):
if n <= 1: # база: дальше не идём
return 1
return n * fact(n - 1) # шаг: задача поменьше
fact(4) = 4fact(3) = ... = 4321. Каждый вызов уменьшает n, упирается в базу и «разворачивается» обратно. Без базы был бы бесконечный спуск (RecursionError).
Мне помогло рисовать стек вызовов на бумаге: каждый вызов — коробочка, ждёт результат следующей. Дошёл до базы — коробочки закрываются снизу вверх.
Если мы будем бесконечно уменьшать число (n-1, n-2...), мы дойдем до нуля. Что такое 0? Математики договорились, что это 1. Это и есть точка остановки. Если мы не остановимся, то уйдем в минус и программа упадет. def factorial(n): # 1. Базовый случай (выход из петли) if n == 0: return 1 # 2. Рекурсивный случай (зовем сами себя) else: return n * factorial(n - 1)