recursion - Given a recursive function, how do I change it to tail recursive and streams?

Question

Given a recursive function in scheme how do I change that function to tail recursive, and then how would I implement it using streams? Are there patterns and rules that you follow when changing any function in this way?

Take this function as an example which creates a list of numbers from 2-m (this is not tail recursive?)

Code:

(define listupto
  (lambda (m)
    (if (= m 2)
        '(2)
        (append (listupto (- m 1)) (list m)))))

Answer 1

I'll start off by explaining your example. It is definitely not tail recursive. Think of how this function executes. Each time you append you must first go back and make the recursive call until you hit the base case, and then you pull your way back up.

This is what a trace of you function would look like:

(listupto 4)
| (append (listupto(3)) '4)
|| (append (append (listupto(2)) '(3)) '(4))
||| (append (append '(2) '(3)) '(4))
|| (append '(2 3) '(4))
| '(2 3 4)
'(2 3 4)

Notice the V-pattern you see pulling in and then out of the recursive calls. The goal of tail recursion is to build all of the calls together, and only make one execution. What you need to do is pass an accumulator along with your function, this way you can only make one append when your function reaches the base case.

Here is the tail recursive version of your function:

(define listupto-tail
  (lambda (m)
     (listupto m '())))

# Now with the new accumulator parameter!
(define listupto
   (lambda (m accu)
     (if (= m 2)
        (append '(2) accu)
        (listupto (- m 1) (append (list m) accu)))))

If we see this trace, it will look like this:

(listupto 4)
| (listupto (3) '(4))  # m appended with the accu, which is the empty list currently
|| (listupto (2) '(3 4)) # m appended with accu, which is now a list with 4
||| (append '(2) '(3 4))
'(2 3 4)

Notice how the pattern is different, and we don't have to traverse back through the recursive calls. This saves us pointless executions. Tail recursion can be a difficult concept to grasp I suggest taking a look here. Chapter 5 has some helpful sections in it.