Чтобы понять рекурсию, нужно понять рекурсию.
Автор неизвестен
Рекурсия — это такой способ организации обработки данных, при котором программа вызывает сама себя. Рекурсия называется прямой тогда, когда программа вызывает сама себя непосредственно или косвенной — когда программа вызывает саму себя опосредованно, через вызов других программ. Соответственно метод, который внутри своего тела вызывает сам себя, называется рекурсивным методом. Количество вложенных вызовов метода называется глубиной рекурсии.
Существует ряд задач, при решении которых обоснованным является использование именно рекурсивных методов. Например, вычисление различных рекуррентных последовательностей, в которых каждый следующий член, начиная с некоторого, определяется через предыдущие значения.
Стек вызовов
Чтобы понять, как работает рекурсивный метод, нужно знать, как распределяется память во время исполнения программы. В текущий момент времени может исполняться только один единственный метод из всей программы. Это значит, что, если метод а () вызывает в своем теле метод b (), а сам а () вызывается в main (), то при запуске программы управление сначала будет передано методу main (), затем методу а (), затем методу b (). Метод b () вернёт результат и управление в а (), а ()вернет результат и управление в main (), и только потом будут выполняться команды, указанные в методе main ()в строках, записанных после строки с вызовом a ().
Вся иерархия вызовов хранится в специальной области памяти, называемой стеком вызовов. Элементы в этот участок памяти добавляются по принципу LIFO: последний добавленный элемент должен быть извлечён первым. Когда метод вызывает сам себя, новым локальным переменным и параметрам выделяется место в стеке и код метода выполняется с этими новыми начальными значениями. При каждом возврате из рекурсивного вызова старые локальные переменные и параметры удаляются из стека, и выполнение продолжается смомента вызова внутри метода.
