Оглавление > Глава 3. Рекурсия
Рекурсия - вызов функцией самой себя.
Рекурсию в программировании всегда можно заменить циклом. Рекурсия применяется тогда, когда решение становится более понятным. Применение рекурсии не ускоряет работу программы: более того, решение с циклами иногда работает быстрее.
Циклы могут ускорить работу программы. Рекурсия может ускорить работу программиста. Выбирайте, что важнее в вашей ситуации!
Рекурсивная функция состоит из двух частей:
- базовый случай
- рекурсивный случай
В рекурсивной функции обязательно нужно указать базовый случай, в котором не будет очередного рекурсивного вызова. Иначе возникнет бесконечный цикл и стек вызовов переполнится.
Самый известный пример рекурсии - вычисление факториала
Код:
factorial(3); // 6
factorial(6); // 720
factorial(1); // 1
factorial(-1); // Error
Команда для проверки:
npm run factorial
Стек - структура данных, в которой новые элементы добавляются в начало и извлечение элементов происходит из начала. Последним пришел, первым ушел - LIFO.
В виде стека устроено выполнение программы в компьютере. Каждая вызываемая функция создает в стеке новый блок, который сразу же начинает выполняться.
При бесконечном рекурсивном цикле стек вызовов быстро заполняется.