- Рекурсивная подпрограмма — это функция или процедура, которая вызывает сама себя непосредственно или через другие подпрограммы.
- Рекурсивная функция обязательно должна содержать условие завершения (базовый случай), чтобы предотвратить бесконечную рекурсию и зацикливание программы. Каждый рекурсивный вызов создает новый набор локальных переменных и параметров, что приводит к использованию стека вызовов.
- Преимущества и недостатки:
- плюсы: упрощает решение задач, которые естественно описываются рекурсивно (обход деревьев, задачи разделяй и властвуй);
- минусы: увеличивает потребление памяти (из-за стека вызовов) и может замедлять выполнение программы по сравнению с итеративными решениями.
- Области применения: алгоритмы на графах, сортировка, обработка сложных структур данных, математические вычисления (факториал, числа Фибоначчи).
Пример. Рекурсивная функция, которая выводит целые числа от заданного положительного числа N до 1 в порядке убывания. Каждое число должно выводиться через пробел.
Программный код | Окно вывода |
|---|---|
#include <iostream> | 10 9 8 7 6 5 4 3 2 1 |