1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

String reversal using recursion

  1. Aug 9, 2014 #1

    Maylis

    User Avatar
    Gold Member

    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.
    ImageUploadedByPhysics Forums1407566948.526315.jpg
     
  2. jcsd
  3. Aug 9, 2014 #2

    rcgldr

    User Avatar
    Homework Helper

    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), ...
     
  4. Aug 9, 2014 #3

    Maylis

    User Avatar
    Gold Member

    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.
     
  5. Aug 9, 2014 #4

    verty

    User Avatar
    Homework Helper

    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.
     
  6. Aug 9, 2014 #5

    rcgldr

    User Avatar
    Homework Helper

    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);
    }
     
     
  7. Aug 9, 2014 #6

    Maylis

    User Avatar
    Gold Member

    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))
     
  8. Aug 9, 2014 #7

    rcgldr

    User Avatar
    Homework Helper

    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.
     
  9. Aug 9, 2014 #8

    Maylis

    User Avatar
    Gold Member

    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.
     
  10. Aug 9, 2014 #9

    rcgldr

    User Avatar
    Homework Helper

    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: String reversal using recursion
  1. Recursive function (Replies: 16)

  2. Recursion Tree (Replies: 3)

  3. Recursive calls (Replies: 15)

Loading...