Почему рекурсия так важна?
- Рекурсия — это очень важная концепция в программировании, которую необходимо освоить, чтобы эффективно работать со структурой данных при написании алгоритмов и решении задач.
- Графики и деревья — это естественные рекурсивные структуры данных.
Что такое рекурсия?
Проще говоря, рекурсия — это цикл
Если рекурсия и итерация — это циклы, чем они отличаются?
- Рекурсия занимает дополнительное место в стеке. Мы знаем, что рекурсия занимает дополнительное место в стеке памяти для каждого рекурсивного вызова, что потенциально может иметь большую сложность пространства по сравнению с итерацией.
- Рекурсия обеспечивает более чистый и читаемый код. Несмотря на то, что требуется больше места, использование рекурсии может сделать ваш код более читабельным по сравнению с итерацией.
Две фазы рекурсии
- базовый случай
- рекурсивный случай
Рекурсия — это функция, которая многократно вызывает себя в меньших формах с идеей, что сложную проблему можно решить проще, решив меньшую версию той же проблемы.
Что делает рекурсия
- повторяйте вызов все меньшей и меньшей версии самого себя, пока не получите наименьший возможный случай
- этот наименьший случай является базовым случаем
- Затем вы используете ответ на этот базовый случай, чтобы решить следующую наименьшую проблему, затем следующую, затем следующую и так далее, пока не вернетесь к исходной проблеме, с которой вы начали.
Краткое содержание
- У нас есть одна фаза, идущая к базовому случаю.
- У нас есть еще одна фаза, возвращающаяся из базового случая.
Первая фаза перехода от исходного рекурсивного вызова к базовому варианту называется этап вызова.
Второй этап возврата от базового варианта к исходному рекурсивному вызову называется этап возврата.
Итерация состоит только из фазы вызова, а рекурсия состоит из фазы вызова и фазы возврата.
