Рекурсия в программировании

Если вы смеетесь над анекдотом про пиво и бесконечное число математиков*, то 50% успеха в понимании рекурсии уже есть. Рекурсия - это функция, которая вызывает сама себя. В идеале - по условию.

Однажды моя бабушка потеряла в комоде 200 советских рублей заначки. Это была сумма, которую нужно искать! И найти. *Смахнула седую слезу*

Отправим бабушку перерывать комод методом рекурсии:

перетряхнуть ящик;
условие:
2.1. если заначка есть - прекратить поиски и налить себе винишка в награду.
2.2. если заначки нет - открыть следующий ящик и проделать с ним операции, начиная с п.1.

Что примечательно в этом случае: функция вызывает сама себя, и есть условие, при котором цикл исполнения функции прекращается.

Представим, что у нас есть комод с бесконечным количеством ящиков, а заначка - в (бесконечность - 1) ящике. Бабуля копается в комоде до сих пор! И будет вечно искать эту заначку, да? На этот случай можно было бы прикинуть, что в день можно перебрать, например, 8 ящиков. Если бабушка потеряла заначку где-то в 1980м году, то например к 1993 году уже можно было не искать - и у нас появляется другое условие для прекращения исполнения функции. Выполняй цикл 4000 дней (на выходных дадим бабуле отдых), или до наступления события, превращающего 200 советских рублей в резаную бумагу.

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

С рекурсией страшно только первые несколько раз, но если ее понять - то жизнь становится во много раз прекраснее. И программистская, и прочая. Чего и вам желаю :)

* Анекдот:

Заходят в бар бесконечное количество математиков.
Первый: пол-литра пива, пожалуйста
Второй: мне четверть литра пива
Третий: 1/8 литра
Четвертый: мне....
Бармен его перебивает: что вы мне мозг выносите? - вот вам литр на всех!

** Строго говоря, анекдот про бесконечно убывающую геометрическую прогрессию. В контексте рекурсивной функции нас интересует бармен, который продолжает наливать математикам пиво до наступления стоп-события (понял, что это математики).