Før det næste eksempel indskyder vi her et ganske kort afsnit, som i tekst gør rede for hvordan rekursive funktioner virker internt.

35.1 Implementation af rekursive funktioner

 

35.1.  Implementation af rekursive funktioner
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

De tre første punkter gør rede for stakken af activation records, som vi har set i både udviklingen af de simple (og kunstige) rekursive kald af f fra afsnit 33.2 og udviklingen af power(2.0,10) omtalt i afsnit 34.6.

Hvert funktionskald kræver afsættelse af en activation record - lager til værdier af aktuelle parametre, lokale variable, og noget "internt bogholderi". En kæde af rekursive funktionskald kræver én activation record pr. kald/inkarnation af funktionen. Man skal være varsom med brug af rekursion som kan afstedkomme mange (tusinder) af rekursive kald. Dette kan føre til 'run time stack overflow'. Der findes en speciel form for rekursion hvor lagerforbruget kan optimaliseres Denne form kaldes halerekursion Halerekursion er tæt forbundet med iterative løsninger (brug af while eller for kontrolstrukturer).

Det sidste punkt (og de to underpunkter) nævner halerekursion (tail recursiveness på engelsk). Vi går ikke i detaljer med halerekursion i dette materiale. Jeg henviser til materialet Functional Programming in Scheme som diskuterer emnet forholdsvis grundigt.