Неделю боролся с осознанием рекурсии, изучаю учебник Learn.Javascript. Пока в голове такая каша:
- Рекурсия это вызов функции внутри себя же, но уже с другим параметром
- В решении конкретной задачи параметр должен уменьшаться или увеличиваться
- Параметр будет уменьшаться/увеличиваться до тех пор пока не запнётся на условии
- Условие на котором запнётся рекурсия должно вернуть простейшее решение уже не требующее очередного вызова функции
- Все предыдущие функции ждут решения следующей, в том числе простейшего решения. Место где они ждут называется Стек (с англ. Stack == стог, стопка)
- Когда рекурсия запнётся на простейшем решении, результаты начнут возвращаться в обратном порядке. Из конца в начало, с глубины на поверхность. Функции которые получили решение будут уходить из Стека начиная с последней. Останется только довольная первая, которая всю эту заварушку устроила.
Следует различать три вещи:
- Рекурсия это общее явление, оно встречается не только в программировании - в природе, рисовании и т.д....
- Чтобы использовать это явление для решения задач, оно должно возвращать нам результат. Нужно объяснить компьютеру с каким шагом двигаться, где остановиться и что возвращать.
- А вот Стек это уже чисто программное явление, т.к. это ячейки компьютерной памяти. На каждом шаге компьютер будет записывать всё что происходит чтобы не заблудиться именно в Стек.
Можно такой пример привести: В армии генерал отправил майора за спиртом, майор отправил капитана за спиртом, капитан отправил лейтенанта за спиртом, лейтенант отправил сержанта за спиртом, сержант отправил рядового за спиртом. Рядовому некого отправлять, это очевидно - он пошёл и нашёл спирт. Затем спирт пошёл обратно по цепочке рядовой - сержант - лейтенант - капитан - майор - генерал. Генерал доволен, всё чётко.
Друзья, сейчас очень нужна ваша критика - дополните или поправьте чтобы лучше понять рекурсию.
function foo() { return foo(); }
тоже вполне рекурсия, хоть и абсолютно бесполезная :)