[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

tail recursion

> The net (modulo storage reclamation) amount of storage space consumed
> by performing any sequence of tail calls p1 => p2 => ... => pn is no
> more than the amount that would be consumed by performing a direct tail
> call from p1 => pn.

This would mean that if I implemented the tail call from p1 => pn in a
very space-consumptive way, that it would be ok to do the same for the
sequence p1 => p2 => ... => pn; but that if I handled p1 => pn nicely,
I would be required to do the same for p1 => p2 => ... => pn.

> The following program should not cause a memory overflow (assuming that
> garbage closures created along the way are reclaimed):
>    (define f (lambda (f) (lambda () ((f f)))))
>    ((f f))

This doesn't follow from the above characterization of tail-recursion,
but it could serve as an alternate definition I guess.  If my
implementation ran this program without overflowing, then it would be
tail-recursive, even if it didn't handle other tail-recursive programs
in the expected way.