bt_bb_section_bottom_section_coverage_image

Rekurzije

Šta su rekurzije?

Rekurzija je tehnika u programiranju gde funkcija poziva samu sebe kako bi rešila neki problem. Da bi rekurzija bila korisna i ispravna, potrebno je definisati osnovni slučaj (base case) koji prekida rekurziju, čime se izbegava beskonačno izvršavanje funkcije.

Možemo reći da rekurzija funkcioniše slično steku – svako pozivanje funkcije stavlja trenutni poziv na vrh steka. Funkcija se izvršava dok ne dođe do osnovnog slučaja. Kada se osnovni slučaj postigne, funkcija počinje da “vraća” vrednosti i uklanja pozive sa steka, redom kako su pozivi bili dodavani.

Primer: Fibonačijev niz

Fibonacijev niz je niz brojeva gde je svaki broj zbir prethodna dva broja. Prva dva broja su obično definisana kao 0 i 1. Matematička definicija je:

  • F(0)= 0
  • F(1) = 1
  • F(n) = F(n−1) + F(n−2), za n≥2
program FibonaciRekurzija;
function Fibonaci(n: Integer): Integer;
begin
if n = 0 then
    Fibonaci := 0
else if n = 1 then
    Fibonaci := 1
else
    Fibonaci := Fibonaci(n - 1) + Fibonaci(n - 2);
end;

var i, broj: Integer;
begin
write('Unesi broj elemenata Fibonacijevog niza: ');
readln(broj);
for i := 0 to broj - 1 do
    write(Fibonaci(i), ' ');
writeLn;
end.
Rekurzije kod lista

Odredjivanje dužine celobrojne liste

function Len(p : IntList) : integer;
begin
if p = nil then
	Len := 0
else
	Len := 1 + Len(p .next)
end;

Odredjivanje sume celobrojne liste

function Sum(p : IntList) : integer;
begin
if p = nil then
	Sum := 0
else
	Sum := p^.n + Sum(p^.next)
end;

Brisanje celobrojne liste

procedure Kill(var p : IntList);
begin
if p <> nil then
	begin
	Kill(p .next);
	dispose(p);
	p := nil
	end
end;
0 komentara

Komentariši