3

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 to 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!

Improve this question
4
  • I believe you mean count-up. Commented Feb 21, 2011 at 23:54
  • oh! I didn't realize it was tail-recursive already. o_o Commented Feb 22, 2011 at 0:20
  • SO is maybe not the best place to ask hw questions. Commented Feb 22, 2011 at 15:11
  • why not? :/ I only know of irc and s.o. as online resources to get help. Commented Feb 22, 2011 at 21:35

1 Answer 1

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

my-reverse is tail-recursive, too.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.