Понятие рекурсии

Лабораторная работа №9 Программирование с использованием рекурсии

Решить задачу рекурсивно – это значит разложить ее на подзадачи, которые затем аналогичным образом (т. е. рекурсивно) разбиваются на еще меньшие подзадачи. На определенном уровне подзадачи становятся настолько простыми, что могут быть решены тривиально.

В рекурсивном алгоритме важно предусмотреть способ его остановки, т.е. ввести условие, при котором рекурсивное обращение к функции прекращается.

Пример выполнения работы

Вычислить среднее значение элементов одномерного массива.

#include <iostream.h>

double Mean_rec(double *A, int n); //прототип рекурсивной функции

double Mean_cyc(double *A, int n); //прототип нерекурсивной функции

void main()

{

double A[10];

int n;

cout << "Enter a size of vector: ";

cin >> n;

cout << "Enter elements of vector:";

for (int i=0; i < n; i++)

cin >> A[i];

cout <<"The mean value by the recursion:";

cout << Mean_rec(A, n) << endl;

cout <<"The mean value by the cycle:";

cout << Mean_cyc(A, n) << endl;

return;

}

double Mean_rec(double *A, int n)

{

if (n > 0)

return A[n - 1] / n + Mean_rec(A, n - 1) * (n - 1) / n;

else

return A[n] / 2;

}

double Mean_cyc(double *A, int n)

{

double mean = 0;

for (int j=0; j < n; j++)

mean = (mean * j + A[j]) / (j + 1);

return mean;

}