17. Рекурсията като метод за програмиране. Рекурсия. Рекурсивни програми и рекурсивни структури от данни.

10.1 Рекурсивни функции в математиката

Ако в дефиницията на някаква функция се използва самата функция, дефиницията на функцията се нарича рекурсивна.

Примери:

а) Ако n е произволно естествено число, следната дефиниция на функцията факториел

е рекурсивна. Условието при n = 0 не съдържа обръщение към функцията факториел и се нарича гранично.

б) Функцията за намиране на най-голям общ делител на две естествени числа a и b може да се дефинира по следния рекурсивен начин:

Тук граничното условие е условието при a = b.

в) Ако x е реално, а n цяло число, функцията за степенуване може да се дефинира рекурсивно по следния начин:

В този случай граничното условие е условието при n = 0.

г) Редицата от числата на Фибоначи

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

се дефинира рекурсивно по следния начин:

В този случай имаме две гранични условия при n = 0 и при n = 1.

Рекурсивната дефиниция на функция може да се използва за намиране стойността на функцията за даден допустим аргумент.

Примери:

а) Като се използва рекурсивната дефиниция на функцията факториел може да се намери факториелът на 4. Процесът за намирането му преминава през разширение, при което операцията умножение се отлага, до достигане на граничното условие 0! = 1. Следва свиване, при което се изпълняват отложените операции.

4! =

4.3! =

4.3.2! =

4.3.2.1! =

4.3.2.1.0! =

4.3.2.1.1 =

4.3.2.1 =

4.3.2 =

4.6 =

24

б) Като се използва рекурсивната дефиниция на функцията gcd, може да се намери gcd(35, 14).

gcd(35, 14) =

gcd(21, 14) =

gcd(7, 14) =

gcd(7, 7) = 7.

В този случай няма разширяване, нито пък свиване. Двата аргумента на gcd играят ролята на натрупващи параметри. Те се променят докато се достигне граничното условие.

в) Като се използва рекурсивната дефиниция на функцията за степенуване може да се намери стойността на 2-4.

г) Чрез рекурсивната дефиниция на функцията, генерираща редицата на Фибоначи, може да се намери fib(5).

fib(5) = 5

В този случай намирането на fib(5) генерира дървовиден процес. Операцията + се отлага. Забелязваме много повтарящи се изчисления, например fib(0) се пресмята 3 пъти, fib(1) 5 пъти, fib(2) - 3 пъти, fib(3) 2 пъти, което илюстрира неефективността на този начин за пресмятане.

10.2 Рекурсивни функции в C++