Рекурсія
Рекурсія - це такий спосіб організації допоміжного алгоритму
(підпрограми), при якому ця підпрограма (процедура або функція) в ході
виконання її операторів звертається сама до себе. Взагалі, рекурсивним називається
будь-який об'єкт, який частково визначається через себе.
Наприклад,
наведене нижче визначення двійкового коду є рекурсивним:
<двійковий код>:: = <двійкова
цифра> | <двійковий код> <двійкова цифра>
<двійкова цифра>:: = 0 | 1
Тут для
опису поняття були використані, так звані, металінгвістіческій формули
Бекуса-Наура (мова БНФ); знак "::=" означає "за визначенням
є ", знак" | "-" або ".
Взагалі, в
рекурсивної визначенні повинно присутньо обмеження, граничне умова,
при виході на яке подальша ініціація рекурсивних звернень припиняється.
Наведемо інші
приклади рекурсивних визначень.
Приклад 1.
Класичний приклад, без якого не обходяться ні в одному оповіданні про рекурсії,
- Визначення факторіалу. З одного боку, факторіал визначається так:
n! = 1 * 2 * 3 *...* n. З іншого боку, 
Граничним
умовою в даному випадку є n <= 1.
Приклад 2.
Визначимо функцію K (n), яка повертає кількість цифр у заданому
натуральному числі n: 
Завдання. За
аналогією визначте функцію S (n), яка обчислює суму цифр заданого натурального
числа.
Приклад 3. Функція
C (m, n), де 0 <= m <= n, для обчислення біноміального коефіцієнта 
по
такою формулою 
є
рекурсивної.
Нижче будуть
наведені програмні реалізації всіх цих (і не тільки) прикладів.
Звернення до
рекурсивної підпрограмі нічим не відрізняється від виклику будь-який інший
підпрограми. При цьому при кожному новому рекурсивної зверненні до пам'яті
створюється нова копія підпрограми з усіма локальними змінними. Такі копії
будуть породжуватися до виходу на граничне умова. Очевидно, у разі відсутності
граничного умови, необмежене зростання числа таких копій призведе до аварійного
завершення програми за рахунок переповнення стека.
Породження все
нових копій рекурсивної підпрограми до виходу на граничне умова називається
рекурсивним спуском. Максимальна кількість копій рекурсивної підпрограми,
яке одновренно може перебувати в пам'яті комп'ютера, називається глибиною
рекурсії. Завершення роботи рекурсивних підпрограм, аж до самої першої,
яка ініціювала рекурсивні виклики, називається рекурсивним підйомом.
Виконання
дій у рекурсивної підпрограмі може бути організовано одним з варіантів:
Begin Begin Begin
P; оператори; оператори;
оператори; P P;
End; End; оператори
End;
рекурсивний
підйом рекурсивний
спуск і рекурсивний узвіз, і
рекурсивний підйом
Тут P --
рекурсивна підпрограма. Як видно з малюнка, дії можуть виконуватися або
на одному з етапів рекурсивного звернення, або на обох відразу. Спосіб
організації дій диктується логікою розробляється алгоритму.
Реалізуємо
наведені вище рекурсивні визначення у вигляді функцій і процедур на мові
Pascal і у вигляді функцій на мові C.
Приклад 1.
(Функція на Pascal)
Function
Factorial (N: integer): Extended;
Begin
If N <= 1
Then Factorial: = 1
Else Factorial: = Factorial (N-1) * N
End;
(Процедура на Pascal)
Procedure Factorial (N: integer; Var
F: Extended);
Begin
If N <= 1
Then F: = 1
Else Begin Factorial (N-1, F); F: = F * N End
End;
/* Функція на C */
double Factorial (int N)
(
double F;
if (N <= 1) F = 1.; else F = Factorial (N-1) * N;
return F;
)
Приклад 2.
(Функція на Pascal)
Function K (N: Longint): Byte;
Begin
If N <10
Then K: = 1
Else K: = K (N div 10) +1
End;
(Процедура
на Pascal)
Procedure K (N: Longint; Var Kol: Byte)
Begin
If N <10
Then Kol: = 1
Else Begin K (N Div 10, Kol); Kol: = Kol 1 End;
End;
/*
Функція на C */
int K (int N)
(int Kol;
if (N <10) Kol = 1; else Kol = K (N/10) 1;
return Kol;
)
Приклад 3.
(Функція на Pascal)
function C (m, n: Byte): Longint;
Begin
If (m = 0) or (m = n)
Then C: = 1
Else C: = C (m, n-1) + C (m-1, n-1)
End;
(Процедура на Pascal)
Procedure C (m, n: Byte; Var R: Longint);
Var R1, R2: Longint;
Begin
If (m = 0) or (m = n)
Then R: = 1
Else Begin
C (m, n-1,
R1);
C (m-1, n-1, R2);
R: = R1 + R2
End;
End;
/* Функція на C */
int C (int m, int n)
(int f;
if (m == 0 | | m == n) f = 1; else f = C (m, n-1) + C (m-1, n-1);
return f;
)
Приклад 4.
Обчислити суму елементів лінійного масиву.
При вирішенні
задачі використовуємо наступне міркування: сума дорівнює нулю, якщо кількість
елементів дорівнює нулю, і сумі всіх попередніх елементів плюс останній, якщо
кількість елементів не дорівнює нулю.
(Програма
на мові Pascal)
Program Rec2;
Type LinMas = Array [1 .. 100] Of Integer;
Var A: LinMas;
I, N: Byte;
(рекурсивні функції)
Function Summa (N: Byte; A: LinMas):
Integer;
Begin
If N = 0 Then Summa: = 0 Else Summa: = A [N] + Summa (N - 1, A)
End;
(Основна
програма)
Begin
Write ( 'Кількість елементів масиву?');
ReadLn (N); Randomize;
For I: = 1 To N Do
Begin
A [I]: = -10 + Random (21); Write (A [I]: 4)
End;
WriteLn; WriteLn ( 'Сума:',
Summa (N, A))
End.
/* Програма на мові C */
# include
# include
# include
# include
int summa (int N, int a [100 ]);
int i, n, a [100];
void main ()
(
clrscr ();
printf ( "nКолічество
елементів масиву? "); Scanf ("% d ", & n);
printf ( "nв
сформованому масиві% d чисел: n ", n);
randomize ();
for (i = 0; i
(a [i] = -10 + random (21); printf ( "% d", a [i ]);}
printf ( "Сума:
% d ", summa (n-1, a ));
)
int summa (int N, int a [100])
(
if (N == 0) return a [0]; else return a [N] + summa (N-1, a);
)
Приклад 5.
Визначити, чи є задана рядок паліндромом, тобто читається однаково
зліва направо і справа наліво.
Ідея рішення
полягає в перегляді рядки одночасно зліва направо і справа наліво і
порівнянні відповідних символів. Якщо в якийсь момент символи не
збігаються, робиться висновок про те, що рядок не є паліндромом, якщо ж
вдається досягти середини рядки і при цьому всі відповідні символи збіглися,
то рядок є паліндромом. Граничне умова - рядок є
паліндромом, якщо вона порожня чи складається з одного символу.
(програма на мові Pascal)
Program
Palindrom;
(рекурсивна
функція)
Function Pal (S: String): Boolean;
Begin
If Length (S) <= 1
Then Pal: = True
Else Pal: = (S [1] = S [Length (S)]) and Pal (Copy (S, 2, Length (S) - 2 ));
End;
Var S: String;
(Основна
програма)
Begin
Write ( 'Введіть рядок:'); ReadLn (S);
If Pal (S) Then WriteLn ( 'Рядок є
паліндромом ')
Else WriteLn ( 'Рядок не
є паліндромом ')
End.
/* програма на мові C */
# include
# include
# include
char s [100];
int pal (char s [100 ]);
void main ()
(clrscr ();
printf ( "nВведіте рядок:");
gets (s);
if (pal (s))
printf ( "Рядок є паліндромом ");
else
printf ( "Рядок не є паліндромом ");
)
int pal (char s [100])
(int l; char s1 [100];
if (strlen (s) <= 1) return 1;
else (l = s [0] == s [strlen (s) -1];
strncpy (s1, s 1, strlen (s) -2);
s1 [strlen (s) -2] = '
