Рекурзивне функције¶
Рекурзивне функције су функције које позивају саме себе. Многи математички и програмерски проблеми су рекурзивни, тако да рекурзивне функције представљају ефикасан начин за њихово решавање.
А шта су заправо рекурзивни проблеми? То су они сложени проблеми до чијег решења се долази решавањем мањих случајева истог тог проблема. Пример из живота би била штедња у банци, односно каматни рачун. Уложите у банку своту новца уз одређену каматну стопу и орочите је на одређени број година. Сваке наредне године основица на коју се обрачунава камата увећава се за камату из претходне године по одређеној формули. Једноставно речено – камата на камату. Овом проблему ћемо се вратити мало касније, кроз задатак.
Заједничка карактеристика рекурзивних проблема је да решавају исти проблем са другим параметрима.
Илустрација рекурзије, Foto: Pinterest:
Типичан пример рекурзије у математици је факторијел неког броја.
Како можемо приказати факторијел броја 5?
5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!;
Општи облик би гласио:
n! = n * (n - 1)!
Видимо да се образац стално понавља до неке вредности, само се мења параметар n.
Међутим, у раду са рекурзивним функцијама мора се бити обазрив. Ако би позив функције био безуслован, рекурзија би се извршавала бесконачно. Зато са рекурзивним функцијама треба баратати пажљиво, односно треба их добро упознати.
Обрати пажњу на следећи пример, где главна функција позива саму себе:
#include<stdio.h>
main()
{
printf("1");
main();
printf("0");
}
Резултат извршавања програма у коме главна функција позива саму себе:
И шта видимо када се изврши програм? Низ јединица! Програм као да је упао у бесконачну петљу. А нула, када ће се одштампати? Одговор је: никада!
Зашто, о чему се заправо ради?
Извршавањем програма штампа се број 1, затим функција main() позива саму себе,
штампа се још једна 1 и све тако редом. Обрати пажњу да се приликом извршавања
сваког примерка функције main() никада није извршила наредба printf("0");.
Овако нешто нема смисла – неопходно је дефинисати услов када треба стати са
рекурзивним позивима.
Погледајмо сада пример рекурзивне функције са условом.
Креираћемо функцију која исписује бројеве од 1 до 3, прво у директном, а затим у инверзном поретку.
void rekurzija(int n)
{
printf("%d", n);
if (n < 3)
rekurzija(n + 1);
printf("%d", n);
}
int main(void)
{
rekurzija(1);
return 0;
}
1 2 3 3 2 1
На почетку извршавања програма у главном програму позивамо функцију rekurzija у
главном програму за n=1.
rekurzija(1);
Анализирајмо шта се дешава у функцији.
Први примерак функције, n=1:
Извршава се први ред функције printf("%d", n) – програм ће штампати 1.
Како је услов испуњен (1 < 3), позива се функција rekurzija (n + 1), односно rekurzija (2).
У првом обраћању функцији друга наредба printf("%d", n) није се извршила.
Ово нам је од суштинске важности, јер нам говори да се функција није извршила до краја.
Други примерак функције, n = 2:
Извршава се први ред функције printf("%d", n) – програм ће штампати 2.
Како је услов испуњен (2 < 3), позива се функција rekurzija(n + 1), односно rekurzija (3).
Као и у првом примерку функције, функција се није извршила до краја.
Трећи примерак функције, n = 3:
Извршава се први ред функције printf("%d", n) – програм ће штампати 3.
Како сада услов није испуњен (3 < 3), функција rekurzija (n + 1) се не позива, већ се
извршава последњи ред функције printf("%d", n) – програм ће штампати 3.
Извршењем ове наредбе последњи примерак позване функције је извршен до краја.
Сада се програм враћа на ниво изнад, на претходни примерак, извршавајући последњу наредбу
printf("%d", n) – програм ће штампати 2.
На исти начин се завршава први примерак функције – програм ће штампати 1.
Након што су се извршили сви примерци функције rekurzija, врши се повратак у главни програм
и наставља се његово извршавање.
Графички приказ извршавања рекурзивне функције:
Да смо извршили позив rekurzija(2), на екрану бисмо добили 2 3 3 2.
А шта да смо позвали функцију за параметар n >= 3? Извршио би се само основни примерак
функције, односно добили бисмо резултат 3 3, 4 4…
Наравно, сложеност рекурзије зависи од наших захтева. Да смо ставили услов у функцији
n < 10, за позив rekurzija(1) функција би била позвана 10 пута и на екрану бисмо добили:
1 2 3 4 5 6 7 8 9 10 10 9 8 7 6 5 4 3 2 1
За вежбу, користећи претходни пример, покушај да урадиш и анализираш функцију која исписује
бројеве од 1 до n прво у инверзном, а затим директном поретку, n, …, 2, 1, 1, 2, ..., n
#include<stdio.h>
void ispis(int n)
{
printf("%d", n);
if (n > 1)
ispis(n - 1);
printf("%d", n);
}
int main(void)
{
int n;
printf("Unesit broj\n");
scanf("%d", &n);
ispis(n);
return 0;
}
Резултат извршавања програма:
Unesi broj 5
5 4 3 2 1 1 2 3 4 5
Задаци за вежбу:
Креирати рекурзивну функцију zbir која рачуна збир првих n природних бројева.
Решење:
Ово је типичан рекурзивни проблем – анализом проблема се може уочити правило. Збир првих
n природних бројева је збир броја n и првих n-1 бројева.
На пример, збир првих 10 бројева је збир броја 10 и збира првих 9 бројева, а збир првих 9 збир броја 9 и збира првих 8, и тако редом све до броја 1. Услов за излазак из рекурзије је када се функцији проследи 0. Тада се као вредност функције враћа 0.
Из наведеног, општи израз је suma(n) = n + suma(n - 1)
#include<stdio.h>
int suma(int n)
{
if (n == 0)
return 0;
return n + suma(n - 1);
}
int main(void)
{
int n;
printf("Unesi n: ");
scanf("%d", &n);
printf("Suma prvih %d prirodnih brojeva je %d", n, suma(n));
return 0;
}
Резултат извршавања програма:
Unesi n: 12
Suma prvih 12 prirodnih brojeva je 78
Креирати рекурзивну функцију stepen која рачуна n-ти степен броја а.
Решење:
На основу анализе једноставног примера \(2^5\)…
… можемо доћи до општег израза \(a^n=a*a^{n-1}\):
#include<stdio.h>
int stepen(int a, int n)
{
if (n == 0)
return 1;
return a * stepen(a, n - 1);
}
int main(void)
{
int a, n;
printf("Unesi a: ");
scanf("%d", &a);
printf("Unesi n: ");
scanf("%d", &n);
printf("%d", stepen(a, n));
return 0;
}
Резултат извршавања програма:
Unesi a: 2
Unesi n: 5
32
Креирати рекурзивну функцију faktorijel за израчунавање n!. У главном
програму исписати факторијеле свих бројева од 1 до 10.
I начин
long faktorijel(int n)
{
if(n == 0)
return 1;
return(n * faktorijel( n - 1));
}
II начин
long faktorijel(int n)
{
if (n > 0)
return(n * faktorijel(n - 1));
return 1;
}
int main(void)
{
int i;
for (i = 0; i <= 10; i++)
printf("%2d! = %ld\n", i, faktorijel(i));
return 0;
}
Резултат извршавања програма:
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
Креирати рекурзивну функцију fibonaci која рачуна n-ти Фибоначијев број. У главном
програму исписати првих n Фибоначијевих бројева.
Фибоначијеви бројеви су они чија је вредност једнака збиру претходна два броја. Прва два члана низа имају вредност 1. На пример, првих девет чланова Фибоначијевог низа су: 1, 1, 2, 3, 5, 8, 13, 21, 34,…
#include<stdio.h>
int fibonaci(int n)
{
if (n > 2)
return fibonaci(n - 1) + fibonaci(n - 2);
return 1;
}
int main(void)
{
int n, i;
printf("Unesi n: ");
scanf("%d", &n);
for (i = 1; i <= n; i++)
printf("%d ", fibonaci(i));
return 0;
}
Резултат извршавања програма:
Unesi n: 10
1 1 2 3 5 8 13 21 34 55
Написати програм који рачуна новчани износ којим располаже улагач после n година
ако је годишња камата р%. Уложени новац је s.
#include<stdio.h>
double iznos(double n, double p, double s)
{
if (n != 0)
return (1 + p / 100) * iznos(n - 1, p, s);
else
return s;
}
int main(void)
{
double n, p, s;
printf("Unesi broj godina: ");
scanf("%lf", &n);
printf("Unesi vrednost kamate u %%: ");
scanf("%lf", &p);
printf("Unesi iznos koji ulazes: ");
scanf("%lf dinara", &s);
printf("\n%.2lf dinara", iznos(n, p, s));
}
Резултат извршавања програма:
Unesi broj godina: 5
Unesi vrednost kamate u %: 7.5
Unesi iznos koji ulazes: 1000 dinara
1435.63 dinara