В этой статье мы попытаемся понять, что же такое рекурсия и зачем она нужна.
Рекурсией называется вызов функцией самой себя. Это достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Один из вариантов увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.
В программировании рекурсия тесно связана с функциями, точнее именно благодаря функциям в программировании существует такое понятие как рекурсия или рекурсивная функция. Простыми словами, рекурсия – определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию).
В каждой рекурсивной функции должно быть два случая: базовый и рекурсивный. Базовый случай - это случай, при котором функция приходит к конечной цели и заканчивает свою работу, а рекурсивный случай - это случай, при котором функция не приходит к своей конечной цели и вызывает сама себя.
Все вызовы функций хранятся в стеке вызовов. Стек - это структура данных, представляющий собой список элементов, организованных по принципу LIFO («последним пришёл — первым вышел»). Зачастую стек реализуется в виде однонаправленного списка (каждый элемент в списке содержит помимо хранимой информации в стеке указатель на следующий элемент стека). Стек поддерживает две операции: занесение и извлечение элементов.