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).
Enhver løkke (ala while, do, for) kan let omprogrammeres med en (hale)rekursiv funktion.
Nogle former for rekursion kan kun meget vanskeligt omprogrammeres med løkker.