Tail-recursion - need help

[hans030390]

I'm not quite sure I understand tail-recursion (especially when it comes to actually doing it/applying it to specific problems). I mostly understand it if I watch someone do it (while explaining), but when it comes to doing it on my own, I either don't know what to do or get stuck.

Here's a specific problem:

Define a procedure count-forwards that takes a nonnegative integer n and returns a list of integers from 0 up to and including n. Hint: define and call a tail-recursive helper procedure.
> (count-forwards 0)
(0)
> (count-forwards 5)
(0 1 2 3 4 5)

I actually think I just figured out what I may need to do (as I typed this), but in the event I still don't, I'd like to have this posted. I appreciate any help anyone can give.

 

[dinkumthinkum]

When you write the helper function, you write some code which looks like this:

if base case?
then do base case
else do recursive case

The recursive case probably performs some computation, then invokes the helper function recursively:

do some computation first,
and finally call helper function recursively

That is sufficient for tail-recursion, because once you call the helper function recursively, you do not do any more computations after it returns.

 

[hans030390]

Originally posted by: dinkumthinkum
When you write the helper function, you write some code which looks like this:

if base case?
then do base case
else do recursive case

The recursive case probably performs some computation, then invokes the helper function recursively:

do some computation first,
and finally call helper function recursively

That is sufficient for tail-recursion, because once you call the helper function recursively, you do not do any more computations after it returns.

Ok...any specific hints as to were to go for that problem I listed? Or maybe I'm just thinking way too much into all of this (at least this problem). I thought tail-recursion was more complicated than that.

 

[deveraux]

My understanding of any recursive problem really is to make a complicated problem simple. Regarding the specific problem you posted, I did not quite implement it the way dinkumthinkum said so maybe he can respond later with how he had envisioned the implementation if it differs significantly from how I have done it.

My approach is to first have a helper function that is passed the interger n. It first checks if n is indeed non-negative (not doing anything if it is). Then it calls itself with n-1 and then prints n.

That pretty much produces the output you desire.

Edit: Doh! I completely blanked the TAIL part. Sorry, this post was complete rubbish, ignore it.

Edit2: Ok, I had another stab at it. I made the helper procedure have 2 variables, one that counted upward from 0 and the other as the input value. This allowed the desired output to be shown since you print the 'counting up' variable till it reached the input value.

 

[dinkumthinkum]

Write this function: (count-forward-helper n lst) returns a list of integers 0 .. n appended to lst.

(count-forwards-helper 2 (list 3 4 5)) ==> (0 1 2 3 4 5)

 

[hans030390]

Originally posted by: dinkumthinkum
Write this function: (count-forward-helper n lst) returns a list of integers 0 .. n appended to lst.

(count-forwards-helper 2 (list 3 4 5)) ==> (0 1 2 3 4 5)

I just checked the assignment...it said we can't use append, because it turns out we actually haven't learned it (like I thought).

 

[dinkumthinkum]

You do not need to use append. I was just using it to describe the function's behavior.

 

[hans030390]

Originally posted by: dinkumthinkum
You do not need to use append. I was just using it to describe the function's behavior.

Oh, ok.

 

[hans030390]

Originally posted by: deveraux
Edit2: Ok, I had another stab at it. I made the helper procedure have 2 variables, one that counted upward from 0 and the other as the input value. This allowed the desired output to be shown since you print the 'counting up' variable till it reached the input value.

Ok, I understand that concept, but I still can't get it to work. I've slowly become more and more confused in this class...right now, I can get my code to count up from 0 (the first variable) until it reaches x, then it stops. But then it returns x. I can understand the concept of why it's doing that, but I can't seem to actually do the work right.

 

[dinkumthinkum]

I have no idea where you're confused. Are you remembering to actually build up a list?

 

[hans030390]

Originally posted by: dinkumthinkum
I have no idea where you're confused. Are you remembering to actually build up a list?

Yeah, I just have some retarded mental block keeping me from figuring out how to do it (counting up from 0 until a specific value).

 

[dinkumthinkum]

(cons 0 (cons 1 (cons 2 (cons 3 (cons 4 (cons 5 nil))))))