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)
        (iter (* counter product)
              (+ counter 1)

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.

  • 3
    Look up tail recursion. Basically this is possible only if every iteration performs the same operation on the same set of variables, with no branching, variation, or post-operation cleanup. That allows you to reuse all variables instead of allocating a new stack frame for each step. Feb 3 '14 at 11:17
  • 2
    It's not that most other languages couldn't do that. They just don't care much about it, so they don't require it in the language standard and common implementations don't bother with it either.
    – user7043
    Feb 3 '14 at 11:19
  • @delna Why the SICP author (Jay Sussman) then says that not being able to do that is a "defect" of other languages? Feb 3 '14 at 11:23
  • 1
    At least in the part you quote, I don't see any claim that they are unable to do so, just that they don't do so. The "defect" is the lack of TCO, not anything in the language design making TCO impossible.
    – user7043
    Feb 3 '14 at 11:29
  • 3
    @KilianFoth: That's not true in general. Some of these shiny new languages perform their own TCO and just generate iterative bytecode. F.ex., Scala even has a @tailrec annotation, which guarantees you tail recursiveness if the compile runs error-free.
    – Frank
    Feb 3 '14 at 13:51

Essentially with tail recursion, the problem with recursion in general is that you each function call gets it's own stack frame. In this stack frame you store all your local variables and whatnot.

So if you run a function like

  int fact(int n){
      if(n == 0)
           return 1;
      return n * fact(n-1);

fact is called n times, allocating n stackframes. If n is big, that's a lot of memory.

There is hope however, when our function is structured in the form

 int f(int x){
     return g(foo); // Function call is in the final position

Then we can throw away f's stack frame before entering g, this means that we won't allocate too many frames as long as we're using simple tail calls. It will actually compile to each function having it's own label and jmping to the tail called function, very fast.

All Schemes is tail recursive, as are most functional languages' implementations like those of SML, OCaml, Haskell, Scala, and (kind of) Clojure. This means that whenever you have a function call as the absolute last thing in your function, it won't allocate a new stack frame. Using this, we can write a do-while loop as follows in Scheme

  (define (do-while pred body)
     (body)                   ;; Execute the body
     (if (pred)               ;; Check the predicate
         (do-while pred body) ;; Tail call
         '()))                ;; Exit

And this runs in exactly the same amount of space as the equivalent imperative code would :) Pretty nifty.

Note, Tail Call Optimization /= Tail Recursion

A common misconception is that TCO is strictly confined to the case where a function tail calls itself. This is a specific subset of TCO and what most JVM languages provide. Languages like Scheme which aren't restricted by the JVM's limitations are properly TCO'd making it possible to say write a DFA which will run in constant memory by tail calling between states.

  • @DocBrown In the case of Scheme the standard specifies that all conforming languages are TCO'd. Of course this is not the case of all languages and TCO is usually just that, a compiler optimization. Feb 3 '14 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.