Рекурсія

Рекурсія - Це такий спосіб організації допоміжного алгоритму (підпрограми), при якому ця підпрограма (процедура або функція) в ході виконання її операторів звертається сама до себе. Взагалі, рекурсивним називається будь-який об'єкт, який частково визначається через себе.

Наприклад, наведене нижче визначення двійкового коду є рекурсивним:

<двійковий код>:: = <двійкова цифра> | <двійковий код> <двійкова цифра>

<двійкова цифра>:: = 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] = '