String reversal using recursion

[gfd43tg]

Homework Statement

Write a function called reverse that uses recursion to reverse any one-dimensional string array.

Homework Equations

The Attempt at a Solution

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.

 

[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), ...

 

[gfd43tg]

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.

 

[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.

 

[rcgldr]

The tree would look something like this:

//
     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):

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);
}

 

[gfd43tg]

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

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

 

[rcgldr]

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

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.

 

[gfd43tg]

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.

 

[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