# String reversal using recursion

1. Aug 9, 2014

### Maylis

1. The problem statement, all variables and given/known data
Write a function called reverse that uses recursion to reverse any one-dimensional string array.

2. Relevant equations

3. The attempt at a solution
Code (Text):
function out = reverse(str)
if length(str) == 0
out = str;
else
out = [str(end) reverse(str(1:end-1))];
end
I am having difficulty understanding how this recursion tree will look. I am using a break point to understand the behavior, and it seems like every iteration it is taking off the last letter of the string until the string is empty, then it is filling it back in reverse order. But I can't put that into the form of a tree.

2. Aug 9, 2014

### rcgldr

There's a level of recursion for every element in the string (which consumes a lot of stack space). At the final depth of recursion, the function returns a null string. The next level up, returns the 1st element, the next level up returns the 2nd element followed by the 1st element, then 3rd element followed by (2nd, 1st), ...

3. Aug 9, 2014

### Maylis

How should the tree of recursive calls look? Does my root node have correct children? I'm trying to do this based off a fibonacci sequence that I wrote recursively where each node had two children with fibnum(n-1) and fibnum(n-2), but that was easier to see on a tree. Now instead of a sum I am appending the end to the recursive function, so I am confused about how the tree should appear.

4. Aug 9, 2014

### verty

It doesn't look right to me. Anyway, there is a trick you don't know about. How would you solve this problem: "Find a recursive procedure to print a string one character at a time." Try to solve that and then find an extremely simple way to modify it to print the string in reverse.

5. Aug 9, 2014

### rcgldr

The tree would look something like this:

Code (Text):

//
node
end-0  node
end-1  node
end-2  node
...
2  node
1  node
0  null

Side note, recursively splitting the string into halves would be better (less stack space):
Code (Text):

std::string rvrs(std::string str)
{
size_t m, n;
if(str.size() < 2)
return(str);
m = str.size()/2;
n = str.size()-m;
std::string left  = rvrs(str.substr(0, m));
std::string right = rvrs(str.substr(m, n));
return(right + left);
}

6. Aug 9, 2014

### Maylis

What you are labeling as node should be reverse(str(1:end-1)), or do the indices change there as well? Like the 2nd layer should be

Code (Text):
reverse(str)
str(end) reverse(str(1:end-1))
str(end-1) reverse(str(1:end-2))
.....
str(1)    reverse(str(1:1))

7. Aug 9, 2014

### rcgldr

Is the goal here to show what the tree looks like during calls or during returns? What I posted is a tree of returned values. The stack isn't really a tree, it's just a set of pointers to concatenated strings, so there's no "left" or "right" on the stack, but only in the concatenation operation performed within the recursive function.

The example code I posted does end up with left and right pointers on the stack, but no nodes, and it's a depth first, left first sequence, so again, it's not really a tree structure.

8. Aug 9, 2014

### Maylis

I was under the impression that the tree looks identical to the calls as the returns, with the exception of how the tree is traversed. Calls are pre-order and returns are post-order, no??

In general I don't understand how to do the trees. My other thread I believe the tree is correct, with the likely exception of the route of traversal. Technically this question doesn't ask anything as far as how many recursive calls are made, I was just wondering out of my own understanding. Perhaps there is a reason that it wasn't asked, it might be something we didn't cover.

9. Aug 9, 2014

### rcgldr

In my opinion, the goal here should be looking at what is on the "call stack". Recursion nests local variables onto the stack, which normally is not considered to a tree structure (as far as I know). A call stack, may optionally include a linked list of "frame pointers", but that's optional (many compilers allow frame pointers to be omitted).

http://en.wikipedia.org/wiki/Call_stack