Рекурсия функциялары

 

Рекурсивдүү функцияларды өзүнчө карап көрөлү. Рекурсивдүү функциялардын кадимки методдордон негизги айырмасы, алар өздөрүнүн ичинен кайра өзүн чакыра алышат.

 

Мисалы, сандын факториалын эсептеген функцияны карап көрөлү:

static int factorial(int x){

    

    if (x == 1){

    

        return 1;

    }

    return x * factorial(x - 1);

}

Биринчиден, шарт текшерилет: эгер киргизилген сан 1ге барабар болбосо, анда бул санды ошол эле функциянын натыйжасына көбөйтөбүз, ага параметр катары х-1 саны өткөрүлөт. Башкача айтканда, рекурсивдүү түшүү пайда болот. Жана башкалар, биз параметрдин мааниси бирге барабар эмес учурга жеткенге чейин.

 

Рекурсивдүү функцияда return операторун колдонгон жана функциянын башында турган кандайдыр бир негизги вариант болушу керек. Факториалдык учурда, бул (x == 1) 1; кайтарылса. Жана бардык рекурсивдүү чалуулар акыры базалык регулярга жакындаган субфункцияларга кайрылышы керек. Ошентип, функцияга оң санды бергенде, кошумча функцияларга кийинки рекурсивдүү чалууларда, аларга ар бир жолу бирден аз сан берилет. Ал эми акырында сан 1ге барабар боло турган абалга жетип, базалык абалды колдонобуз.

 

Бул учурда фактордук аныктоо үчүн циклдердин негизинде оптималдуу чечимдер бар экенин белгилей кетүү керек:

static int factorial(int x){

    int result=1;

    for (int i = 1; i <= x; i++)

    {

        result *= i;

    }

    return  result;

}

Рекурсивдүү функциянын дагы бир кеңири таралган мисалы - Фибоначчи сандарын эсептеген функция. Теорияда Фибоначчи ырааттуулугунун n-мүчөсү төмөнкү формула менен аныкталат: f(n)=f(n-1) + f(n-2), f(0)=0 жана f(1)= 1.

static int fibonachi(int n){

 

    if (n == 0){

        return 0;

    }

    if (n == 1){

        return 1;

    }

    else{

        return fibonachi(n - 1) + fibonachi(n - 2);

    }

}