Tail-recursive?

Question

I'm writing a function that takes a list and returns the sum of the squares of all items in the list. Called on (1 2 3) it should return 14: (1² + 2² + 3²).

I have this sqsum function:

(define (sqsum lis)
    (if (null? lis)
        0
        (+ (* (car lis) (car lis)) (sqsum (cdr lis)))
    )
)

Is this tail recursive? I think it is recursive but not tail recursive. This is part of my homework and I'm not looking for solution: I just want to know if this is tail recursive or not. If not then I need to read more and find new solutions.

Answer 1

To be tail recursive the recursion has to happen at the very last function, i.e. you cannot do anything with the results from the recursiv call. Here you pass it to +, which makes it non-tail-recursive. The compiler could optimize this away though, and it's pretty easy to do yourself too.

Answer 2

No, it is not tail recursive.

The general approach to making a non-tail recursive function tail-recursive is to include an accumulator, which is an extra argument that carries the current evaluation of the procedure through your recursive calls.

Incidentally, this is also where "helper" functions are very useful. The general practice is to define your function so that it does not take the accumulator, define a helper function within it that does take the accumulator, and then have the main function do little besides call the helper function. You'll see what I mean in a sec.

In your case (if I'm remembering my Scheme properly :p):

(define (sqsum lis)
    (define (sqsum-h lis acc)
        (if (null? lis)
            acc
            (sqsum-h (cdr lis) (+ acc (* (car lis) (car lis))))
        )
    )
    (sqsum-h lis 0)
)

This is tail-recursive because the last thing any recursive call does is immediately return the result of another function without modifying it.