Reverse a list of words recursively

Hey,

I am trying to learn recursivity and I am trying to do a program that given a list of words it returns them in a reversed order.

Example:
imput: house tree car
output: car tree house

Now I have some doubts about recursivity: I read the c++ thread about recursivity and it sais that the point of recursivity is to express the cases in function of a simpler case until we get to the base case whose value we know.

Now the thing is, do we even have a base case here? I mean, we don't even know how much words will be entered.

Secondly, how can we express a case in function of a simpler one?

 
To lost to generate a code :p
Assume you have a function Reverse() and a string "word". Then, recursion would progress as follows:

Reverse("word")
"d" + Reverse("wor")
"d" + ("r" + Reverse("wo"))
"d" + ("r" + ("o" + Reverse("w")))
"d" + ("r" + ("o" + "w"))
"d" + ("r" + "ow")
"d" + "row"
"drow"
Last edited on
But i don't intend to reverse the characters of the strings, only the strings as shown in the example. Thats why I can't finde a base case.
Look for spaces and reverse the string according to spaces rather than by character as in Josue Molina's example. He/she's trying to give you the general structure without the answer.

You're going to need the find and substr methods in the string class. If there are no more spaces, then there are no more words. Just follow Josue Molina's example after you figure out how to get the first word, but backwards.
I don't think a recursive approach would be the best for this problem.

What you can do is split the string into tokens that are then stored in a container. Finally, you display the contents of the container in reverse order. Here's a quick example: http://ideone.com/L60EI2

Nevertheless, it's still doable. Just follow GRex2595's instruction.
Last edited on
The recursive approach is the most logical one here.

The recursive principle on a list is this:

I wrote:
If I can do something to the first item in a list with respect to the rest of the list, I can do it to the entire list.


I'm sure that needs a little unraveling.

Example:
Given a list of numbers, can I sum them?

    (1 2 3 4)

The answer, recursively, is yes:

    sum of (1 2 3 4) --> 1 + sum of (2 3 4)

Your question, "what is the base case?" is simple: What is the sum of an empty list? Zero of course.

    1 + sum of (2 3 4)
    1 + (2 + sum of (3 4))
    1 + (2 + (3 + sum of (4)))
    1 + (2 + (3 + (4 + sum of ())))
    1 + (2 + (3 + (4 + 0)))
    1 + (2 + (3 + 4))
    1 + (2 + 7)
    1 + 9
    10



Back to your assignment:

(1) Can you rewrite a list by taking the first element and the rest of the list to reverse the list?

(2) Is there a case where there is no point in trying to reverse the list?

Hope this helps.
Topic archived. No new replies allowed.