Приклади програм

Приклад 1. Дано ціле число n, . Обчислити n! за допомогою функції, яка реалізує такий метод обчислення факторіала:

; , k = 1, 2, 3, …

Розв’язок.

#include <iostream>
using namespace std;

int factorialR(int k); // Прототип функції
// Визначення головної функції
int main()
{
int n;
do
{
cout << "n = ";
cin >> n;
} while (n < 0 || n > 12);
cout << n << "! == " << factorialR(n) << '\n';
system("pause");
return 0;
}

int factorialR(int k)
{
if (k == 0) return 1; //Якщо опорна умова виконана
return k * factorialR (k - 1); //Якщо ні
}

У наведеному тексті функція factorialR() після першого її виклику в головній функції багаторазово звертається сама до себе зі значенням параметра k, яке зменшується від заданого при першому виклику початкового значення n до 0. При досягненні параметром зна­чення 0 вико­нується опорна умова і здійснюється вихід з функції. При цьому відбувається повернення в точку виклику функції на попередньому рівні з продовженням обчислення значення виразу k * factorialR(k - 1) і наступним виходом з функції з повернен­ням на попередній рівень.

Приклад 2. Визначити рекурсивну функцію множення цілих чисел через додавання: , при .

Дано два цілих числа. Знайти їх добуток за допомогою розробленої функції.

Розв’язок.

#include <iostream>
using namespace std;

int Multiplication(int x, int y); // Прототип функції
// Визначення головної функції
int main()
{
int x, y;
cout << "x = ";
cin >> x;
cout << "y = ";
cin >> y;
cout << x << " * " << y << " == " <<
Multiplication(x, y) << '\n';
system("pause");
return 0;
}
int Multiplication(int x, int y)
{
if (y < 0)
{
y = -y;
x = -x;
}
if (y == 0) //Опорна умова
return 0; // Завершення рекурсії
return x + Multiplication(x, y - 1); //Рекурсивний виклик
}

Приклад 3. Визначити і використати рекурсивну функцію підсумову­вання елементів масиву, що містить n дійсних чисел (n £ 20).

Розв’язок.

#include <iostream>
using namespace std;

double SumRecurs(double *a, int Count); // Прототип функції

int main() // Визначення головної функції
{
int n;
double a[20];
do
{
cout << "n = ";
cin >> n;
} while (n < 1 || n > 20);
for (int i = 0; i < n; i++)
{
cout << "a[" << i << "] = ";
cin >> a[i];
}
cout << "Sum == " << SumRecurs(a, n) << '\n';
system("pause");
return 0;
}

double SumRecurs(double *a, int Count) // Визначення функції
{
// Якщо в масиві один елемент, то він і є сумою
if (Count == 1) // Опорна умова
return a[0]; // Завершення рекурсії
// Інакше до останнього елемента додаємо суму решти
//елементів, яка обчислюється рекурсивним викликом функції
return a[Count - 1] + SumRecurs(a, Count - 1);
}

Приклад 4. Дано ціле число n. Отримати нове число, десятковий запис якого співпадає з десятковим записом розвернутого на 180° числа n зі збере­женням знаку. Визначити рекурсивну функцію «розвороту» цілого числа.

Розв’язок.

#include <iostream>
using namespace std;

int ReverseValue(int n, int *p = new int); // Прототип функції

int main() // Визначення головної функції
{
int n;
cin >> n;
cout << ReverseValue(n) << '\n';
system ("pause");
return 0;
}

int ReverseValue(int n, int *p) // Визначення функції
{
if (n / 10 == 0) // Опорна умова
{
*p = 10;
return n; // Завершення рекурсії
}
else
{
int k; // Нижче здійснюється рекурсивний виклик
return (k = ReverseValue(n / 10, p) + n % 10 * *p,
*p *= 10, k);
}
}

Функція ReverseValue() має два параметри: n – число, що «розверта­ється», p – вказівник, що вказує на комірку пам’яті для збереження і наро­щу­вання цілого степеня числа 10. Другий параметр є параметром за умовчан­ням; тому до функції можна звертатися як з одним параметром, так і з двома. Зна­ченням за умовчанням є адреса комірки динамічної пам’яті, відведення якої здійснюється при першому виклику функції ReverseValue(). У тілі функції здійснюється багаторазове звернення її до самої себе з першим фактичним па­раметром n / 10, що відповідає «відсіканню» цифри в запису числа n (самої крайньої праворуч). Оператор return повертає досить незвичне зна­чення (k = ReverseValue(n / 10, p) + n % 10 * *p, *p *= 10, k), в яко­му використовується операція «кома». При цьому в змінну k запи­сується роз­вер­нута на 180° частина числа, до якої ліворуч «дописується» цифра (остача від ділення), яка перед підсумовуванням помножується на степінь числа 10 (а саме, *p), після чого значення *p помножується на 10 (*p *= 10). Значенням же виразу в дужках є значення змінної, яка записано після другої коми. Почат­ковим значення змінної *p є число 10, записуване при виконанні опорної умови.

Особливістю алгоритму розв’язання наведеної вище задачі є те що в про­цесі виконання алгоритму повинні змінюватися дві величини – оброблюване число і степінь десяти, на значення якого помножується остача від ділення. При цьому оброблюване число повинне починати зменшуватися з першого рівня ре­курсивних викликів, а початкове значення степеня (за яке береться число 10) може бути задане тільки на останньому рівні перед завершенням рекурсивного процесу.

Наведений вище код рекурсивної функції базується на використанні вка­зівника в якості її другого параметру. Можна запропонувати рекурсивну функ­цію, яка не використовує вказівники:

#include <iostream>
using namespace std;

int ReverseValue(int n); // Прототип функції

int main() // Визначення головної функції
{
int n;
cin >> n;
cout << ReverseValue(n) << '\n';
system ("pause");
return 0;
}

int ReverseValue(int n) // Визначення функції
{
static int p;
if (n / 10 == 0) // Опорна умова
{
p = 10;
return n; // Завершення рекурсії
}
else
{
int k; // Нижче здійснюється рекурсивний виклик
return (k = ReverseValue(n / 10) + n % 10 * p,
p *= 10, k);
}
}

Ця версія рекурсивної функції ReverseValue()ґрунтується на викорис­танні статичної локальної змінної (цілочислова змінна p), яка оголошується всередині її коду. Особливістю статичних локальних змінних є те що вони роз­поділяються в пам’яті один раз при першому зверненні до функції і зберігають своє значення при виході з функції і повторному вході в неї. Функція побудо­вана так, що змінна p отримує своє початкове значення 10 тільки по завершенні останнього рівня рекурсії (при виконанні опорної умови), яке збільшується від рівня до рівня при зворотному проходженні.

Приклад 5. Дано дійсне число та непарне натуральне число n. Об­числити

.

Розв’язок.

#include <iostream>
using namespace std;

double Value(double x, int n, int k = 1); // Прототип функції

int main() // Визначення головної функції
{
double x;
int n;
cout << "x = ";
cin >> x;
do
{
cout << "n = ";
cin >> n;
} while (!(n > 0 && n % 2 == 1));
cout << "Result = " << Value(x, n) << '\n';
system ("pause");
return 0;
}

double Value(double x, int n, int k) // Визначення функції
{
if (k == n) // Опорна умова
return x / n; // Завершення рекурсії
// Нижче здійснюється рекурсивний виклик
return x / (n - 2 + Value(x, n, k + 2));
}

Код функції ґрунтується на співвідношенні:

Третій параметр функції Value є параметром зі значенням за умовчан­ням. Цей параметр змінюється від 1 (саме це значення задається за умовчанням) до n з кроком 2 при переході з одного рівня рекурсії до іншого.

Приклад 6. Дано дійсні числа a, b, c, d₁, d₂ (d₁ ≤ d₂) і близьке до 0 додатне число ε. Відомо, що на інтервалі [d₁, d₂] рівняння має корінь і цей корінь єдиний. Знайти корінь рівняння методом поділу відрізка навпіл. Вважати, що будь-яка точка інтервалу [d₁, d₂] є коренем, якщо довжина інтер­валу менше ε. Розробити рекурсивну функцію пошуку вказаним методом коре­ня рівняння однієї змінної з трьома коефіцієнтами.

Розв’язок.

#include <iostream>
#include <conio.h>

using namespace std;

double Root(double d1, double d2, double eps,
double a, double b, double c); // Прототип
double f(double x, double a, double b, double c); // Прототип
int main()
{
double a, b, c;
double d1, d2, epsilon;
cout << "a = ";
cin >> a;
cout << "b = ";
cin >> b;
cout << "c = ";
cin >> c;
cout << "d1 = ";
cin >> d1;
cout << "d2 = ";
cin >> d2;
cout << "epsilon = ";
cin >> epsilon;
double x = d1;
cout << "x = " << Root(d1, d2, epsilon, a, b, c) <<'\n';
getch();
return 0;
}
// Визначення рекурсивної функції
double Root(double d1, double d2, double eps,
double a, double b, double c)
{
if (fabs(d1 - d2) < eps) // Опорна умова
return d1; // Завершення рекурсії
// Підготовка до рекурсивного звернення
double x = (d1 + d2) / 2;
if (f(d1, a, b, c) * f(x, a, b, c) <= 0)
d2 = x;
else
d1 = x;
return Root(d1, d2, eps, a, b, c); // Рекурсивний виклик
}
// Визначення звичайної функції
double f(double x, double a, double b, double c)
{

// Замість функції a * sin(b * x + c) можна взяти іншу
return a * sin(b * x + c);
}