Зачем нам рекурсия?
Любую проблему можно решить как рекурсивным методом, так и итеративным методом. Но всякий раз, когда у нас есть проблема, которую сложно решить с помощью итеративного/циклического метода. Затем мы собираемся разделить задачу на меньший экземпляр той же задачи, что означает, что мы решаем ее рекурсивным методом.
Что такое стек вызовов?
Стек вызовов — это структура данных стека, которая используется для отслеживания последовательности вызова функции. Когда вызывается функция, она заталкивается внутрь стека, а когда функция возвращает, она извлекается из стека.
Три концепции рекурсии
- Базовый вариант (завершающий)
- Небольшая проблема
- Логика обработки
Типы рекурсии:
Хвостовая рекурсия:
Если рекурсивная функция вызывает саму себя, и этот рекурсивный вызов является последним оператором в функции. После этого вызова нет ничего, он ничего не выполняет.
Головная рекурсия:
Если рекурсивная функция вызывает сама себя, и этот рекурсивный вызов является первым оператором в функции, и некоторые операции выполняются после вызова. У функции нет процессора для выполнения какой-либо операции в момент вызова. Он должен сделать все во время возвращения.
Линейная рекурсия:
Линейно-рекурсивная функция — это функция, которая один раз вызывает сама себя каждый раз при запуске функции. Ему есть что обрабатывать до и после звонка.
Читать полную статью здесь — Что такое рекурсия? | Концепции рекурсии