Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|PrologElm19}} * 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 …”

2012-10-21T20:09:17Z

Új oldal, tartalma: „{{GlobalTemplate|Infoalap|PrologElm19}} * 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 …”

Új lap

{{GlobalTemplate|Infoalap|PrologElm19}}

* 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'''

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

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.

<pre>
% 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).
</pre>

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.

[[Category:Infoalap]]

A jobbrekurzió fogalma - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|PrologElm19}} * 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 …”