Приклади рекурсій

Розглянемо рекурсивну функцію, що обчислює n-й член послідовності чисел Фібоначчі. Ці числа визначаються рекурентним співвідношенням

для n > 0, f₁ = 1, f₀ = 0.

Приведемо програмну реалізацію даної функції.

#include <iostream>

using namespace std;

long Fib(long n)

{

if (n<2)return n;

else return Fib(n-1)+Fib(n-2);

}

void main()

{

int i;

for (i=0;i<=5;i++)

cout<<Fib(i)<<"\t";

}

У результаті буде виведений наступний ряд чисел Фібоначчі:

0 1 1 2 3 5

Кожен виклик функції Fib при n>1 породжує два вкладених виклики. У результаті відбуваються повторні обчислення тих самих величин і загальна кількість вкладених викликів зростає експоненціально. Цей процес ілюструє рис. 10.1, на якому числа відповідають значенням параметра n.

Рис.10.1. Вкладені рекурсивні виклики функції, що повертає число Фібоначчі

Наприклад, виконання функції Fib(5) призведе до того, що виклик Fib(3) буде здійснено двічі, виклики Fib(2) та Fib(0) – тричі, а виклик Fib(1) – п’ять разів. Загальна кількість вкладених викликів сягне п’ятнадцяти. Тому для практичного використання така програма непридатна.

«Індійський алгоритм» піднесення числа x до натурального степеня n реалізує таке рекурсивне означення степеня числа:

Тривіальний спосіб піднесення числа x до степеня n потребує, щоб виконувались n – 1 операцій множення: x множиться на x, добуток знову множиться на x, і так n – 1 разів. Застосування індійського алгоритму дає можливість значно скоротити кількість операцій. Наприклад, обчислення x¹⁰ за індійським алгоритмом потребує лише чотирьох операцій множення замість дев’яти. Справді, . Тобто, при обчисленні x¹⁰ операції виконуватимуться в такому порядку:

1) обчислюємо x²;

2) x² підносимо до квадрата і отримуємо x⁴;

3) x⁴ множимо на x і отримуємо x⁵;

4) x⁵ підносимо до квадрата і отримуємо x¹⁰.

Наведене вище рекурсивне означення степеня числа може бути реалізоване рекурсивною функцією. При рекурсивному зануренні така функція обчислюватиме значення n/2, а при виході з рекурсії обчислюватиметься множник і виконуватиметься операція множення. Оскільки n%2 дорівнює нулю, якщо n – парне, і дорівнює одиниці, якщо n – непарне, то величина дорівнюватиме 1 за парних значень n і дорівнюватиме x за непарних значень n. Отже, наведемо деталізований індійський алгоритм піднесення до степеня та його програмну реалізацію.

Алгоритм обчислення xⁿ

1. Якщо показник степеня дорівнює нулю, то значення xⁿ покласти рівним одиниці та вийти з рекурсії, інакше виконати дії, зазначені в пунктах 2–5.

2. Якщо показник степеня дорівнює одиниці, то значення xⁿ покласти рівним x та вийти з рекурсії, інакше виконати дії, зазначені в пунктах 3–5.

3. Обчислити значення та піднести його до квадрата.

4. Якщо показник степеня непарний, то обчислене в пункті 3 значення помножити на число x, а отриманий результат вважати значенням xⁿ.

5. Інакше, коли показник степеня парний, то обчислене в пункті 3 значення вважати значенням xⁿ.

Наведемо програмну реалізацію індійського алгоритму.

#include <iostream>

using namespace std;

//Функція піднесення x до степеня n

long powxn(long x, long n)

{

if(n==0) return 1;

if(n==1) return x;

long t;

t = powxn(x,n/2)*powxn(x,n/2);

if (n&1)return t*x;

else return t;

}

void main()

{

cout<<"2^8 = "<<powxn(2,8);

}

У результаті виконання програми отримаємо:

2^8 = 256

Тепер опишемо залежність глибини рекурсії від значення степеня n. У кожному наступному вкладеному виклику значення аргументу n менше від попереднього значення принаймні вдвічі. Оскільки за умови n = 1 розпочинається рекурсивне повернення, то таких зменшень значення аргументу n не може бути більше log₂ n. Отже, глибина рекурсії не перевищує log₂n. Таку глибину можна вважати ознакою високої ефективності алгоритму. Під час виконання кожного рекурсивного виклику відбувається не більше ніж одна операція ділення, піднесення до квадрата та множення, тому загальна кількість арифметичних операцій не перевищує 3log₂n. Якщо величина n достатньо велика, це суттєво менше, ніж n–1 множень. Наприклад, за умови n = 1000 кількість арифметичних операцій приблизно дорівнює 30.

Контрольні питання

1. Що таке рекурсія?

2. Переваги та недоліки рекурсивного програмування.

3. Наведіть власний приклад рекурсії та проаналізуйте глибину рекурсії.

4. Наведіть приклад рекурсії розрахунку факторіалу числа.

5. Наведіть приклад рекурсії розрахунку n-го члену послідовності Фібоначчі.

6. Наведіть алгоритм піднесення числа x до натурального степеня n.