Страницы

Поиск по вопросам

вторник, 12 марта 2019 г.

Правильно ли я понял рекурсию?

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


Ответ

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

Комментариев нет:

Отправить комментарий