Рекурсивные функции

Рекурсивная функция - это функция, которая вызывает саму себя. Это в случае прямой рекурсии. Существует и косвенная рекурсия - когда две или более функций вызывают друг друга. Когда функция вызывает себя, в стеке создаётся копия значений её параметров, после чего управление передаётся первому исполняемому оператору функции. При повторном вызове процесс повторяется. Рекурсивные функции являются альтернативой циклам. Рассмотрим примеры рекурсивных функций для вычисления факториала числа, суммы чисел в заданном интервале и возведения числа в степень.

Пример 1. Вычислить факториал числа. Использовать рекурсивную функцию.

Решение. Организуем ввод пользователем числа, которое является фактическим параметром функции. Условием окончания рекурсии будет равенство введённого числа нулю. В этом случае функция более не вызывает саму себя.

Код C++

#include <iostream> using namespace std; int fact(int n); int main() { int a; cout << "Enter number: " << endl; cin >> a; cout << fact(a) << endl; return 0; } int fact(int n) { int f; if (n == 0) f = 1; else f = n * fact(n - 1); return f; }

Пример 2. Вычислить сумму чисел в интервале, заданном вводимыми числами. Использовать рекурсивную функцию.

Решение. Условием окончания рекурсии станет ситуация, когда верхняя граница на единицу больше нижней границы, то есть интервал задан двумя соседними целыми числами.

Код C++

#include <iostream> using namespace std; int sum(int y, int x); int main() { int a, b; cout << "Enter 1-st number: " << endl; cin >> a; cout << "Enter 2-st number: " << endl; cin >> b; cout << sum(b, a) << endl; return 0; } int sum(int y, int x) { int s = 0; if ((y - 1) == x) s = y + x; else s = y + sum(y - 1, x); return s; }

Итак, видим, что каждая рекурсивная функция должна включать в себя условие окончания рекурсии, иначе рекурсия будет бесконечной, что приведёт к аварийному завершению программы.

Пример 3. Возвести заданное число в заданную степень. Использовать рекурсивную функцию.

Решение. Здесь условием окончания рекурсии будет равенство нулю числа-степени. Обязательно следует предусмотреть вызовы функции для чётной степени и нечётной степени.

Код C++

#include <iostream> using namespace std; int power(long int x, unsigned int y); int main() { int a, b; cout << "Enter number: " << endl; cin >> a; cout << "Enter power: " << endl; cin >> b; cout << power(a, b) << endl; return 0; } int power(long int x, unsigned int y) { int d = 0; if (y == 0) d = 1; else if (y == 1) d = x; else if (y % 2 == 0) d = power (x * x, y/2); else d = x * power(x * x, y/2); return d; }

Ещё один пример рекурсивной функции приведён в уроке "Обход в глубину графа, представленного матрицей инцидентности".

Весь блок Программирование C++

К началу страницы

Поделиться с друзьями