Rekurzió

A programozási nyelvekben a rekurzióról akkor beszélünk, amikor egy program saját magát hívja (önrekurzió), vagy ha több alprogram hívja egymást (kölcsönös rekurzió).

A rekurzív problémák rekurzív alprogrammal viszonylag egyszerűen megoldhatók, azonban ez a megoldás idő és memóriaigényes. Minden rekurzív problémának létezik iteratív megoldása is (és fordítva), amely általában nehezebben programozható, de több szempontból hatékonyabb a rekurzív megoldásnál.

A program futása során az alprogram minden újabb hívásakor újabb memóriaterületet foglal le a veremben a paraméterek és a változók tárolására, ami a memória elfogyásához vezethet. Az ismétlődő hívások miatt pedig a számítási idő nő meg. Ha egy feladat rekurzív megoldásának létezik egy viszonylag jól programozható iteratív (ciklusos) párja, akkor mindig az utóbbi használata javasolt.

A rekurzió végrehajtása során egy úgynevezett báziskritériumot (megállási feltételt) adunk meg, amikor a függvény vagy eljárás már nem hívja meg önmagát.

Faktoriális

A rekurzív működés jól tanulmányozható a faktoriális számítás algoritmusán (nem tipikusan rekurzív feladat).

A faktoriális rekurzív definíciója

n! = 1, ha n=0                         n*(n-1)!, ha n>0

Pl. 4! Kiszámítása

4! = 4*3!

3! = 3*2!

2! = 2*1!

1! = 1*0!

                        4! = 4*3*2*1 = 24

Az általános függvény

Function fakt_rek(n: integer): integer;

Begin

            If (n=0) then result:=1;

                           Else result:=n*fakt_rek(n-1);

End;

A fenti példában az n=0 feltétel a rekurzió befejezésének feltétele. Ekkor az utoljára hívott függvénypéldány 1 értéket ad vissza. Ezt követően a hívási lánc tagjai sorban visszatérnek a megfelelő részeredménnyel. Utoljára a lánc első eleme, az általunk hívott függvény fejezi be működését, megadva a kívánt faktoriális értéket.

A faktoriális iteratív definíciója

0! = 1              n! = n(n-1)(n-2)...(n-k+1)

Az általános függvény

Function fakt_it(n:integer): longint;

Begin

            S:=1;

            For i:=1 to n do S:=S*i;

            Result:=s;

End;

Fibonacci

A Fibonacci-féle számsorozat

0,1,1,2,3,5,8,13,21,34,... (a sorozat egy új eleme az előző kettő összegéből képezhető)

Megoldás rekurzióval

Lefelé haladva egyszerűsítjük az értékeket, amíg Fib(0)=0 vagy Fib(1)=1 nem lesz az eredmény. Ezen megoldás hátránya, hogy nem veszi észre, ha már egy részeredményt kiszámolt.

Function Fib(n: integer): integer;

Begin

If (n=0) then result:=0

   Else

             If (n=1) then result:=1

                            Else

                                     Result:=Fib(n-1)+Fib(n-2);

End;

Ha a sorozat 1-ről indul, és nem 0-ról, akkor: if (n=0) or (n=1) then result:=1;

                                                                            Vagy:  if (n<2) then result:=1;

Megoldás iterációval

Funtion Fib_it(n: integer): integer;

Begin

UE:=1; U:=1;           {Utolsó Előtti, Utolsó elem} {A sorozat 1-ről indul}

For i:=3 to n do begin

                                       F:=U+UE;

                                       UE:=U;

                                       U:=F;

                             End;

Ackermann

A kétváltozós Ackermann-függvény: A(x,y). Már A(10,10) esetén is nagy számokat generál, és egyre több számítást igényel.

Ha (m=0) akkor A(0, n)=n+1

Ha (m>0) és (n=0) akkor A(m, 0):=A(m-1, 1)

Ha (m>0) és (n>0) akkor A(m, n):=A(m-1, A(m, n-1))