Scheme: changing recursion to tail recursion

I'm unsure of how to turn count-forwards into a tail-recursive program. It takes a non-negative number, n, and returns the list of integers from 0 t开发者_如何学Goo n (including n).

Edit: Okay, I finally got this one to work. The problem wasn't that my current program was recursive and I needed to make it tail-recursive- It was just plain wrong. The actual answer is really short and clean. So if anyone else is stuck on this and is also a total programming noob, here's a few hints that might help:

1) Your helper program is designed to keep track of the list so far.

2) Its base case is.. If x = 0.. what do you do? add 0 onto.. something.

3) Recur on x - 1, and then add x onto your list so far.

4) When you get to your actual program, count-forwards, all you need is the helper. But remember that it takes two arguments!

The only recursive function here is list-reverse. It is tail-recursive, because the call to itself is the last operation in the function body.

Your function for generating a nondecreasing sequence from zero to m, which contains the successive results of adding 1 to the previous element, would look something like:

(define (my-reverse lst)
  (define (rev-do xs ys)
    (if (empty? xs)
        ys
        (rev-do (cdr xs) (cons (car xs) ys))))
  (rev-do lst empty))

(define (seq m n)
  (seq-do m n (list m)))

(define (seq-do m n xs)
  (if (= m n)
      (my-reverse xs)
      (let ((next (add1 m)))
        (seq-do next n (cons next xs)))))

(define (seq-from-zero m)
  (seq 0 m))

Test:

> (seq-from-zero 10)
(0 1 2 3 4 5 6 7 8 9 10)

seq-do is a general function for generating nondecreasing sequences from m to n; it is tail-recursive, because the last operation is the call to itself.

I've also implemented reverse from scratch, so that you can use it in your homework problems.