Столкнулся с ситуацией, когда преподаватель объясняет рекурсию очень сложно, на примерах, которые годятся для людей более менее помнящих что такое школьная математика. Для меня, к сожалению, математика - это что-то туманное из далёкого прошлого. Да, факториал и числа Фибоначчи - это круто, и их нахождение для изучения рекурсии подходит как нельзя лучше. Но для меня и многих студентов это проблема. Изучать что-то на основе того, что не помнишь, да и вспоминать не хочешь - такое себе занятие.
Попытаюсь объяснить рекурсию в картинках, максимально просто.
Рекурсия - вызов функции (процедуры) из неё же самой.
Существуют функции, которые не требуют для своей работы ничего, запускаешь её и получаешь результат. Так же есть функции, которые "берут" нечто и трансформируют во что-то другое, не всегда полезное. :) Функции похожи на шляпу волшебника, в которую положили яблоко и через секунду из неё выпрыгнул кролик.
Вот рекурсивная функция - это такая функция, которая "берёт" нечто для получения результата, но делает это забавным образом, вызывая саму себя. В общих чертах принцип её работы похож на матрёшку.
Вот такой порядок действий демонстрирует рекурсию:
- Берём матрёшку, проверяем что её можно открыть. Если открывается - открываем.
- Берём ту, что внутри первой - проверяем что можно открыть. Если открывается, открываем.
- Берём третью, проверяем что можно открыть - открываем.
- Берём следующую, проверяем - НЕ открывается! Это так называемый "базовый случай". Мы достигли максимальной глубины вложенности.
Теперь у нас есть целая матрёшка, которая не открывается.
- Берём верхнюю часть предыдущей - третьей, соединяем с нижней. Получили целую матрёшку, третью по счёту.
- Берём верхнюю часть предыдущей -второй, соединяем с нижней. Получили целую матрёшку, вторую по счёту.
- Берём верхнюю часть предыдущей - первой, соединяем с нижней. Получили целую матрёшку, самую первую.
В итоге: была одна матрёшка, стало четыре! Это результат работы функции.
Рекурсивная функция - "взять матрёшку, проверить, что открывается, если да, то вновь "взять матрёшку, проверить..." и так до момента пока матрёшка не перестанет открываться. С этого момента матрёшки начинаем закрывать, пока перед нами не будет целый ряд собранных.
Теперь в картинках.
Теперь пример на JavaScript.
Результат работы функции:
Немного рекурсии в котах для поднятия настроения!