In order to avoid causing a stack overflow during recursion, do the following:
- Ensure each recursive call is a tail call
- Decorate the recursive function(s) with
thunk
(in the case of co-recursive functions, decorate both). This exposes atrampoline
function, which is used in the next step. - Append a call to
trampoline
to only the initial call to each decorated function. Conversely, do not append a call totrampoline
to any recursive call to athunk
-decorated function.
For example, suppose we have the following naive recursive implementation of the factorial
function: