Рекурентни редици и рекурсия
Рекурентни редици и рекурсия
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) , ),...,,(121−=nnaaafa
то равенството (1.1) се нарича рекурентна зависимост и се казва, че редицата удовлетворява тази рекурентна зависимост. S
Определение 2. Нека е най-малкото цяло число, такова, че при определени стойности на равенството (1.1) определя еднозначно стойността на за . Стойностите се наричат начални условия за рекурентната зависимост. k k a a a ,...,,2 1 nakn>kaaa,...,,21
Задачите, за чието решение се изисква рекурсивен алгоритъм могат да бъдат групирани по следния начин:
-
1. По дадена рекурентна зависимост и съответни начални условия за нея, да се определи рекурсивна функция, пресмятаща –тия член на редица, удовлетворяваща тази рекурентна зависимост. n
Примерни задачи:
Зад. 1. 1. Да се напише рекурсивна функция за изчисляване на , където е редицата на Фибоначи, определена с рекурентната зависимост: nF,......,,,10nFFF
1,11021==+=−−FFFFFnnn
Зад. 1. 2. Да се напише рекурсивна функция за изчисляване стойността на функцията на Акерман , дефинирана за 0 с помощта на рекурентната зависимост: ),(nmAck,0≥≥nm
МАТЕМАТИКА, ИНФОРМАТИКА И КОМПЮТЪРНИ НАУКИ Велико Търново 2006 399
1),0(+=nnAck
)1,1()0,(−=mAckmAck
Други реферати:
Скрининг и профилактика на онкологичните заболявания. Участие на медицинската сестра
Основи на анатомо-физиологията на черния дроб, жлъчния мехур и жлъчните пътища
Соматопатология-пищови
Туберкулоза. Лекарствена ресистентност
Хипертония в детска възраст
Изтегли реферата