Kako Napraviti Rekurzivnu Funkciju U Programskom Jeziku C

Kada sam se prvi put susreo s programiranjem programskog jezika C, najteže mi je bilo shvatiti rekurzivne funkcije. To su funkcije koje pozivaju same sebe . Većinom rješenja zadataka s rekurzijom su jako kratka, ali teško razumljiva. U ovom članku pokazat ću vam kako napraviti program s rekurzijom i pokušati objasniti kako funkcioniraju rekurzivne funkcije.

Najpopularniji zadatak u školama, fakultetima koji ide uz rekurziju je ispis Fibonaccijevog broja.

Malo Povijesti :

Leonardo od Pise (1170-1250), poznat još kao Fibonacci, postavio je 1202.g. u svom radu Liber abaci” tzv. (nerealističancan) problem zečeva”.
Shema razmnožavanja zečeva je slijedeća:
Svaki par zec- zečica (starih barem 2 mjeseca) tijekom svakog slijedećeg mjeseca dobiju par
mladih (zeca i zečicu). Pretpostavlja se da zečevi nikad ne umiru.
Pitanje: Ako smo na početku godine počeli s jednim novorođenim parom, koliko će biti
ukupno parova zečeva početkom slijedeće godine, odnosno općenito nakon n mjeseci?

Matematičko rješenje ovog problema je sljedeće

fibonaccijevi  zecevi

 

Na prikazanoj slici “n” predstavlja broj mjeseci ,a “F(n)” predstavlja parove zečeva , kao što vidimo u 1. i 2. mjesecu imamo samo jedan par zečeva, jer još nisu sposobni za razmnožavanje, u trećem mjesecu imamo 2 para, u 4. mjesecu imamo 3 para (orginalni par i njihovi potomci 3. i 4. mjesecu) itd. Da ne duljim više s matematikom , formula po kojoj se rješava Fibonaccijev problem je
F(0) = 1
F(1) = 1
i
F(n) = F(n-1) + F(n-2); za n veće ili  jednako 2

KADA možemo riješiti neki problem rekurzivnom funkcijom ? Rekurzija se koristi ako se neki posao, zadatak ili sl. može razbiti u korake, ako pogledam primjer Fibonnacija vidimo da ga možemo razbiti u dva djela:
1. dio za n (mjesece) manje od 2 rješenje je 1
2. dio za n (mjesece) veće ili jednako 2 rješenje je F(n-1) + F(n-2)

Idući korak kod izrade rekurzije je definiranje uvjeta, prvo definirajte uvjete pa tek onda ostalo.
Ako pogledamo Fibonnacija vidimo da imamo dva uvjeta
kada je n manji od 2 i kada je n veći ili jednak 2 . Nakon definiranja uvjeta obično slijedi return koji vraća samu početnu funkciju ali s malo drugačijim argumentima i često se tim pozivom još zbraja ili množi neki broj. Da bi ste shvatili kako napraviti rekurzivnu funkciju , morate znati kako funkcionira evaluiranje rekurzije. Ako proguglate malo rekurziju , pronaći će te dosta objašnjena, ali većina su jako komplicirana i potrebno je par sati da bi se u potpunosti razumjela. Ovdje ću vam pokazati kako evaluiranje funkcionira na najjednostavniji mogući način, bar po mom mišljenu. Idealno , ako imate par sati do ispita , a nemate pojma o rekurziji.

 

Programski  kod:

int fib (int n)
 {
 if(n<= 1) return n ;
return fib (n−1) + fib (n−2);

}

Ja evuluiranje rekurzije shvaćam kao stablo koje mora doći do dna pa se vratiti do vrha. Kada ide prema dnu pozivaju se funkcije sa raznim argumentima, a kada ide prema vrhu , vraćaju se (retun) vrijednosti , kad dođete skroz do vrha to je onda prava vraćena vrijednost. Biti će vam razumljivije na sljedećim slikama .
Pogledajmo primjer za gore navedeni programski kod , fibbonacijevu funkciju ,
recimo da unutar maina , pozovemo funkciju s argumentom 4

fib(4);

Stablo crtam na sljedeći način :

1. Pozivamo funkciju fib(4) , nacrtam kružić i unutra broj 4, koji predstavljaju poziv funkcije s argumentom broj 4
4

2) 4 ne ispunjava uvjet (n<= 1) , pa će se izvršiti return fib(n-1)+fib(n-2) =fib(3) + fib(2) , budući da će se pozvati dvije funkcije s argumentima 3 i 2 , onda crtam dva kružića s elementima 3 i 2 , kao podstablo

3 i 2

3) 3 ne ispunjava uvjet (n<= 1) pa će se pozvati fib(2)+fib(1) , 2 ne ispunjava uvjet (n<=1) pa će se pozvati fib(1) +fib(0)

stablo fibonaci

4)2 ne ispunjava uvjet pa će pozvati fib(0) i fib(1)

rekurzija 2

5) Stigli smo do kraja, imama nacrtano stablo , sada moramo ići unazad tj. prema gore , zatvarati sve funkcije koje
smo pozvali , r=1 na crtežu predstavlja return = 1 , krećemo od dna tj. najniže razine stabla i penjemo se prema vrhu , kružić s elementom 1 će vratiti n tj. 1 jer zadovoljava uvjet
if(n<= 1) return n ;

kružić s elementom 0 također zadovoljava uvjet pa će vratiti nulu

razina 1

 

6) Najnižu razinu smo lagano riješili sad idemo na sljedeću razinu , kružić s elementom 2 , ima dva podstabla kružiće s elementima 1 i 0 , ako pogledamo naredbu return fib (n−1) + fib (n−2); vidimo da radimo zbrajanja nad pozivima funkcije, budući da kružići u našem stablu predstavljaju pozive , za rezultat returna zbrajamo sve returne od djece tj. podstabla kružića . Za kružiće 1 i 0 skroz desno vraćamo n , tj, 1 i 0 jer ispunjavaju uvjet if(n<= 1) return n ;

stablo 3

7) Slijedimo gore opisani postupak, dok ne dođemo do vrha , vrijednost r na vrhu, korijenu stabla je rezultat naše rekurzije, znači dobili smo za n=4 , rezultat 3 , to znaći za 4 mjeseca dobijemo 3 para zečeva, ako pogledamo na vrhu posta matematičku sliku , vidim oda je točan rezultat, probajte a neki drugi n , npr. n=6 .

stablo konacno

Nadam se da ste razumjeli kako napraviti stablo , da bude još jasnije pokazati ću na još jednom primjeru za sljedeći zadatak : Treba izraćunati faktorijele n! pomoću rekurzivne funkcije.
Primjer faktorijela:
5! = 5*4*3*2*1
4!=4*3*2*1
3!=3*2*1

ako pogledamo postupak kojim se dobivaju faktorijeli , lako utvrdimo da posao možemo podijeliti na dva djela
npr.
5! = 5 * 4!
4!=4 *3!
općenito vrijedi n!=n * (n-1)!
bog toga taj posao možemo riješiti rekurzivnom funkcijom, programsko rješenje našeg problema je sljedeće:

unsigned long Faktorijela( int Broj ) {
if( Broj < 0 ) return 0; /*Ako je broj negativan, vrati nulu*/
if( Broj < 2 ) return 1; /*Ako je broj jednak 0 ili 1, vrati 1*/
return Broj * Faktorijela( Broj-1); /*Inace koristi rekurzivnu relaciju*/
}

Stablo za recimo n=4 , crtamo na sljedeći način :

rekurzija faktorijel

Opet vidimo da dolazimo do točnog rješenja 24 , ako pogledamo matematički 4!= 4*3*2*1 = 24

Iz svega priloženog dolazimo do sljedeće procedure rješavanja rekurzije , po mom mišljenju najbolja i najjednstavnija :

1. korak

Utvrditi da li se problem, posao može podijeliti na dva djela , ako može problem, posao se može riješiti rekurzivnom funkcijom.

2. korak

Definirati if uvjete , poslije uvjeta gotovo uvijek dolazi return 0 ili 1.

3. korak

Nacrtati ili zamisliti stablo, na temelju stabla napisati rekurzivnu funkciju , rekurzivna funkcija je jako slična početnoj, jedina razlika je u argumentima i još se zbraja, množi ili oduzima neki broj.

Nadam se da vam je ovaj članak pomogao , to je način na koji ja shvaćam rekurziju . Ako imate kakva pitanja, objavite u komentarima.

Odgovori