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

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

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,...,...,,21naaana

1. (1. 1) , ),...,,(121−=nnaaafa

то равенството (1.1) се нарича рекурентна зависимост и се казва, че редицата удовлетворява тази рекурентна зависимост. S

Определение 2. Нека е най-малкото цяло число, такова, че при определени стойности на равенството (1.1) определя еднозначно стойността на за . Стойностите се наричат начални условия за рекурентната зависимост. k k a a a ,...,,2 1 nakn>kaaa,...,,21

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

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

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

Зад. 1. 1. Да се напише рекурсивна функция за изчисляване на , където е редицата на Фибоначи, определена с рекурентната зависимост: nF,......,,,10nFFF

1,11021==+=−−FFFFFnnn

Зад. 1. 2. Да се напише рекурсивна функция за изчисляване стойността на функцията на Акерман , дефинирана за 0 с помощта на рекурентната зависимост: ),(nmAck,0≥≥nm