Примеры задач, решаемых при помощи рекурсии и разработка программного модуля на языке C++

Примеры решения задач при помощи рекурсии

Задача 1. Числа Фибоначчи

Рекурсия по своей сути схожа с методом математической индукции. В данном случае база индукции соответствует базе рекурсии. А в основе предположения индукции лежит предположение о том, что необходимая процедура подготовлена заранее. Шагу индукции можно сопоставить вызов генерируемой рекурсивной процедуры. И, разумеется, существует необходимость предусматривать хотя бы одно условие прерывания процесса.

Далее следует рассмотреть конкретные примеры решения практических задач.

Числа ряда Фибоначчи представляют собой последовательность, каждый следующий элемент равен сумме двух предыдущих элементов. Таким образом, зная два предшествующих элемента, искомый элемент последовательности можно вычислить по следующей формуле (1):

(1),.

Где Fn — искомый элемент последовательности Исходный код программы нахождения N-го числа ряда Фибоначчи будет выглядеть следующим образом:

#include «stdafx.h» .

#include.

using namespace std;

int Fn (int n).

{.

if (n < 3).

return 1;

return Fn (n — 2) + Fn (n — 1);

}.

int main ().

{.

setlocale (LC_ALL, «Russian»);

int n = 0;

cout << «Введите порядковый номер числа: «;

cin >> n;

cout << n <<" -м числом в ряде Фибоначчи является число «<< Fn (n) << endl;

system («pause»);

return 0;

}.

С результатом работы представленного кода можно ознакомиться на рисунке 3.

На данном примере, достаточно просто проследить увеличение затрат ресурсов на исполнение. Если на одной и той же машине результаты для чисел до 30-го числа включительно выдаются практически мгновенно, а для 35-го числа задержка составляет значительно меньше одной секунды, то для 40-го числа программа выдает результат, лишь спустя две секунды, а для 41-го через 6 секунд.

Задача 2. Нахождение факториала

#include «stdafx.h» .

#include.

using namespace std;

int fact (int n).

{.

if (n==1 || n==0) return 1;

return n* fact (n — 1);

}.

int main ().

{.

setlocale (LC_ALL, «Russian»);

int n = 0;

cout << «Введите число «;

cin >> n;

cout << «Факториал числа «<< n << «равен «<< fact (n) << ««;

system («pause»);

return 0;

}.

Результат работы кода представлен на рисунке 4.

Рисунок 4 — Факториал.