### 13 April 2013 4:56 pm (scheme | guile)

In The Little Schemer you are asked to write the function + using the functions *zero?*, *add1* and *sub1*, such as the result of *(+ 46 12)* is *58*.

(define add1 (lambda (n) (+ n 1))) (define sub1 (lambda (n) (- n 1)))

The solution given is:

(define o+ (lambda (n m) (cond ((zero? m) n) (else (add1 (o+ n (sub1 m)))))))

which is correct but has a little problem.

If you are like me (hopefully not), you might have read twenty times the first chapters of SICP (and haven't gone any further). Remember about recursive and iterative processes and recursive procedures? In our *o+* case we have a *recursive procedure* that generates a *recursive process*, as the process generates a chain of deferred *add1* operations.

With a recursive process we can easily blow our stack:

scheme@(guile-user)> (o+ 10 100000) While executing meta-command: ERROR: Throw to key `vm-error' with args `(vm-run "VM: Stack overflow" ())'.

This is because this will generate:

(add1 (add1 (add1 (add1 .... (add1 10)))))

with as many *add1* as *m*.

So, how to improve this? With a recursive procedure that generates an *iterative process*:

(define o+ (lambda (n m) (cond ((zero? m) n) (else (o+ (add1 n) (sub1 m))))))

which will generate:

(o+ 11 99999) (o+ 12 99998) ... (o+ 100010 0)

and doesn't overflow the stack.

scheme@(guile-user)> (o+ 10 100000) $1 = 100010

Yes, this is a tail-recursive function.

11 July 2016 6:30 pm

Aaah, I see it now.