Рекурентни редици и рекурсия 

Recurrence   Relations   and   Recursion:  

A   method   for   teaching   the   topic   of   “Recursion”   in   the 

programming course is developed in this article. It also uses the recurrent-sequences knowledge, gained 
from discrete-mathematics course. 

Key words: 

recurrence relation, recursion 

ВЪВЕДЕНИЕ 

Рекурсията е един от методите, даващ възможност за постигане на кратко и елегантно 

решение   на   определен   клас   задачи.   В   същото   време   тя   е   една   от   „парливите”   теми   в 
обучението по програмиране. Една от причините за това е, че в много от случаите, когато 
за   съответната   задача   съществува   итеративно   решение,   се   препоръчва   избягване   на 
рекурсията. Друга причина са трудностите при преподаването и усвояването на темата. 
Оказва се, че същността на рекурсията като метод за решаване на даден проблем, най-
често остава неразбрана за по-голямата част от обучаемите. Предмет на настоящата статия 
е един подход за представяне на принципите на рекурсията пред студентите в курса по 
Програмиране,  като се използват знанията за рекурентни  редици, получени  в курса  по 
Дискретна математика. 

РЕКУРЕНТНИ РЕДИЦИ И РЕКУРСИЯ. 

Сама по себе си рекурсията не е алгоритъм, а метод за построяване на алгоритми. Тя 

съвсем   естествено   може   да   бъде   приложена   в   случаите,   когато   решаването   на   дадена 
задача с определена размерност може да бъде сведено до решаването на аналогична задача 
с по-малка размерност. Това я доближава до същността на рекурентните редици – редици, 
при които всеки следващ елемент се получава от предходните по определено правило. 

Определение 1. Нека редицата е редицата . Ако може да се изрази като функция на 

предишните елементи на редицата S,...,...,,

21n

aaa

n

a

1 (1. 1) , ),...,,(

121−

=

nn

aaafa

то   равенството   (1.1)   се   нарича  

рекурентна   зависимост  

и   се   казва,   че   редицата 

удовлетворява тази рекурентна зависимост. S

Определение 2. Нека е най-малкото цяло число, такова, че при определени стойности 

на   равенството   (1.1)   определя   еднозначно   стойността   на   за   .   Стойностите   се   наричат 

начални условия 

за рекурентната зависимост. k 

k 

a a a ,...,,

2 1 n

akn>

k

aaa,...,,

21

Задачите,   за   чието   решение   се   изисква   рекурсивен   алгоритъм   могат   да   бъдат 

групирани по следния начин: 

11. По дадена  рекурентна  зависимост  и съответни  начални  условия  за  нея, да се 

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

Примерни задачи: 

Зад. 1. 1. 

Да се напише рекурсивна функция за изчисляване на , където е редицата на 

Фибоначи, определена с рекурентната зависимост: 

n

F,......,,

,10n

FFF

1,1

1021

==+=

−−

FFFFF

nnn 

Зад. 1. 2. 

Да се напише рекурсивна функция за изчисляване стойността на функцията 

на Акерман , дефинирана за 0 с помощта на рекурентната зависимост: ),(nmAck,0≥≥nm 

МАТЕМАТИКА, ИНФОРМАТИКА И КОМПЮТЪРНИ НАУКИ 

Велико Търново 2006 399 

1),0(+=nnAck 
)1,1()0,(−=mAckmAck