Рекурзивне функције

Рекурзивне функције су функције које непосредно или посредно позивају саме себе. Оне омогућавају лако и разумљиво решавање проблема који су, по својој природи, рекурзивни.

Општа карактеристика свих рекурзивних проблема је да се решавање своди на решавање истог проблема са измењеним параметрима. Приликом програмирања то значи да рекурзивна функција позива саму себе са измењеним аргументима. Да би се овакав поступак икада завршио, мора да постоје неке специјалне вредности параметара за које резултат није дефинисан рекурзивно. Резултати специјалних вредности обично су константе.

Пример: Дефинисати функцију која одређује n-ти Фибоначијев број (Фибоначијев низ је низ код кога се n-ти члан низа добија као збир претходна два члана низа, при чему су први и други члан једнаки 1):

 

Написати програм који исписује првих n Фибоначијевих бројева, по десет у сваком реду.

#include<stdio.h>
int fibo (int n)
{
return (n>2)?fibo(n-1)+fibo(n-2):1;
}
main()
{
int nmax,n;
printf("nmax?");scanf("%d",&nmax);
for(n=1;n<=nmax;n++)
{
printf("%6d",fibo(n));
if(n%10==0||n==nmax)printf("\n");
}
}

Рекурзивна решења су, по правилу, мање ефикасна од итеративних решења (помоћу циклуса) истих проблема. Поред тога, дешава се да рекурзивно решавање траје предуго, или тражи неприхватљиво много оперативне меморије за чување међустања између рекурзија.

Имамо дефинисану функцију која исписује бројеве 1,2,3…n прво у инверзном, а затим у директном поретку:

void xxx(int n)
{
printf("%d",n);
if (n>1) xxx(n-1);
printf("%d",n);
}

Ако је n=1 извршавају се само прва и трећа наредба тако да се исписује

11

За n=2 прво се изврши наредба 1 (испис броја 2), а затим, пошто је n>1 реализује поновно обраћање функцији xxx(1). То значи да се у меморији креира други примерак функције (копија тела функције) са својом локалном променљивом n која добија вредност 1. Иза друге наредбе првог примерка функције извршава се прва наредба другог примерка – исписује се 1. Како је n=1, услов n>1 није задовољен, што значи да ће се извршити наредба којом се исписује n, после чега други примерак функције завршава рад. У тачки * ослобађа се меморија коју је заузимао други примерак функције. Извршавање првог примерка функције се наставља од места обраћања другом примерку функције. После исписа вредности n завршава се рад и другог примерка функције. Према томе, обраћањем xxx(2) из главног програма исписује се:

2112

За n=3 у меморији се одваја простор за три примерка функције xxx. Обраћањем из главног програма са xxx(3) исписује се:

321123

Лако је уочити да се са повећањем n драстично повећавају меморијски захтеви за чување n примерака функције, јер у једном тренутку у меморији постоји n различитих примерака функције.

Није тешко приметити да се задатак могао решити и без рекурзивне функције.

Ако се неки проблем лако решава итеративно (коришћењем циклуса) онда треба радити итеративно. Рекурзивно решавање тражи превелики програмерски напор.

Програмски језик C подржава писање рекурзивних функција. Механизам чувања стања функција пре рекурзивног позива и обнављања стања по повратку из рекурзивног позива дешава се аутоматски. На тај начин програмеру не остаје ништа друго, него да рекурзивну дефиницију проблема, такорећи дословце, претвори у одговарајуће изразе на језику C.

Ако се рекурзивно постављени проблем пажљиво претвори у рекурзивну функцију за решавање тог проблема, постоји велика вероватноћа да ће све да функционише исправно. Програмер и не мора да разуме у детаље како ради та функција. Али ако се направи и најмања грешка, откривање те грешке је обично много теже него у случају итеративних функција.

Advertisements

Оставите одговор

Попуните детаље испод или притисните на иконицу да бисте се пријавили:

WordPress.com лого

Коментаришет користећи свој WordPress.com налог. Одјавите се / Промени )

Слика на Твитеру

Коментаришет користећи свој Twitter налог. Одјавите се / Промени )

Фејсбукова фотографија

Коментаришет користећи свој Facebook налог. Одјавите се / Промени )

Google+ photo

Коментаришет користећи свој Google+ налог. Одјавите се / Промени )

Повезивање са %s