common-lisp Recursion
Remarks
Lisp is often used in educational contexts, where students learn to understand and implement recursive algorithms.
Production code written in Common Lisp or portable code has several issues with recursion: They do not make use of implementation-specific features like tail call optimization, often making it necessary to avoid recursion altogether. In these cases, implementations:
- Usually have a recursion depth limit due to limits in stack sizes. Thus recursive algorithms will only work for data of limited size.
- Do not always provide optimization of tail calls, especially in combination with dynamically scoped operations.
- Only provide optimization of tail calls at certain optimization levels.
- Do not usually provide tail call optimization.
- Usually do not provide tail call optimization on certain platforms. For example, implementations on JVM may not do so, since the JVM itself does not support tail call optimization.
Replacing tail calls with jumps usually makes debugging more difficult; Adding jumps will cause stack frames to become unavailable in a debugger. As alternatives Common Lisp provides:
- Iteration constructs, like
DO,DOTIMES,LOOP, and others - Higher-order functions, like
MAP,REDUCE, and others - Various control structures, including low-level
go to
