Люди не часто в повседневной жизни сталкиваются с необходимостью понимания рекурсии, если их деятельность не связана с алгоритмическими вычислениями или программированием. И если вдаваться в математическое объяснение, то всё будет выглядеть довольно сложно, но в данной заметке я попытаюсь максимально просто объяснить что это понятие под собой подразумевает.
Мало кто осознает, но если смотрел вот этот отрывок из мультика "Ну, погоди" то уже сталкивался с рекурсией:
В данном отрывке строка песни "У попа была собака он её любил..." в конце обращается сама к себе, что приводит к бесконечному развитию сюжета в котором поп в песне пишет на камне историю о том как поп пишет на камне историю о том как поп пишет... ну и так далее.
И вот тут мы можем вывеси простое определение рекурсии: Это обращение объекта внутри себя к самому себе, или когда объект является частью себя самого, тут уже кому как удобней. Этого вывода нам вполне хватит для понимания использования этой концепции в программировании.
Рекурсия в программировании это ситуация при которой некая вычислительная операция реализует часть своей логики с помощью обращения к себе же самой. Или другими словами это функция которая внутри вызывает сама себя.
На рисунке выше приведен пример небольшой программы, которая вычисляет факториал заданного числа (в примере это 5). Для тех кто не помнит то факториал числа это произведение всех чисел на числовой прямой, начиная с этого числа и до единицы. Факториал от 0 это единица (так уж решили, иначе все факториалы были бы нулевыми). А именно, в нашем примере факториал числа 5 это 5 * 4 * 3 * 2 * 1 = 120.
Новичики часто допускают ошибку, не указывая уловия выхода из этой цепочки, и проваливаются в бесконечную рекурсию, что приводит к переполнению количества допустимых обращений которые могут храниться в памяти компьютера. Ведь каждое обращение из которого делается обращение к самому себе компьютеру нужно запомнить, и завершить вычисления когда наконец эти обращения прекратятся.
В нашем примере остановка произойдет когда в функцию попадет значение 1, это 2 и 3 строки кода. После того как цепочка вызовов завершится единицей, начнется возврат программы к тем функциям которые ждали завершения вызовов внутри себя. А произойдет это потому, что каждый новый раз мы вызываем функцию с аргументом n уменьшенном на единицу. Если бы мы этого не делали, то вызовы просто никогда бы не закончились.
С философской точки зрения, рекурсия никогда не кончается однажды начавшись, но в реальном мире этого конечно же не происходит, во всяком случае наш образ мышления не позволяет нам осознать бесконечность или выразить её как-то иначе, кроме как показать начало и закончить фразой "и так далее...".
Если хотите прокачаться в Python с нуля, то приглашаю на свой авторский курс Python: Быстрый старт.
Спасибо за внимание!