A jobbrekurzió fogalma

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

• fejezetek: 4.3.1
• fóliák: II.50-52

Az általános rekurzió költséges, helyben és időben is.

Jobbrekurzióról beszélünk, ha:

• a rekurzív hívás a klóztörzs utolsó helyén van, vagy az utolsó helyen szereplő diszjunkció egyik ágának utolsó helyén van stb. ÉS
• a rekurzív hívás pillanatában nincs választási pont a predikátumban (a rekurzív hívást megelőző célok determinisztikusan futottak le, nem maradt nyitott diszjunkciós ág).

Jobbrekurzió optimalizálás: az utolsó hívás végrehajtása előtt a predikátum által lefoglalt hely felszabadul ill. szemétgyűjtésre alkalmassá válik. (Ez az optimalizálás nemcsak rekurzív hívás esetén, hanem minden utolsó hívás esetén megvalósul /last call optimisation/).

A jobbrekurzió így tehát nem növeli a memóriaigényt, korlátlan mélységig futhat. Az imperatív nyelvek ciklusai a hosszuktól függetlenül, konstans veremhasználattal átírhatók rekurzióra.

Példa: számlisták összegzése

Adott számlista elemeinek összegét kell előállítani:

Első megoldás

% sum(+L, ?S): Az L számlista elemeinek összege
sum([], 0).
sum([X|L], S):-
	 sum(L, S0), S is S0+X.

Ahhoz, hogy ezt jobbrekurzív alakra hozzuk, egy háromagumentumú eljárást kell definiálni: sum(L,S0,S) feladata az, hogy S0 adott számértékhez hozzáadja L összes elemét, és az eredményt adja ki S-ben.

% sum_list(+L, ?S): L számlista elemeinek összege
% sum jobbrekurzív valotzata
% SICStus Prologban a lists konyvtarban megtalalhato
sum_list(L, S):-
	 sum(L, 0, S).

% sum(+L, +S0, ?S): Az L számlista eleminek osszege S-S0
sum([], S, S).
sum(X|L, S0, S):-
	 S1 is S0+X,
	 sum(L, S1, S).

Vegyük észre, hogy a sum/3 eljárás fejkommentjében az L, S0 es S közötti összefüggést írtuk le és nem a korábbi meghatározást, amely egy kicsit imperatívabb volt a szükségesnél.