10

Рекурсия

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

Примери:

а
) Ако 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 =