I am starting to learn Lisp, using the SICP book. The authors mention that a procedure (i.e. function) can be recursive or iterative. Additionally, the process those procedures will generate will also be recursive or iterative, and that, surprisingly, a recursive procedure can sometimes generate an iterative process.
The example given is the factorial procedure, which is a recursive procedure, but which generates an iterative process:
(define factorial n) (iter 1 1 n)) (define (iter product counter max-count) (if (> counter max-count) product (iter (* counter product) (+ counter 1) max-count)))
And here's a quotation from the book:
One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. The implementation of Scheme we shall consider does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure.
Question: I understood the principles involved (i.e. the what) but I still don't understand how the Lisp interpreter/compiler will generate an iterative process from a recursive function, being able to calculate it using constant space, and why most other languages are not able to do it.