1. Not finding help here? Sign up for a free 30min 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!

How do recursions work exactly?

  1. Nov 13, 2012 #1
    I don't know why but I am finding it quite unintuitive and confusing. I have an exam coming tomorrow so I have to make sure that I understand it correctly.

    I know that recursion functions as a loop due to its circulatory nature. However, I don't know exactly what is going on within the program to make it loop around here. Can someone clarify?

    Find largest number using recursion.

    function output = maxrec(vec)
    % finds the largest number in a vector recursively.
    % base case, if the vector has a length of 1, reuturn the single element.
    % if not, return the larger of the 2 numbers

    if length(vec) == 1
    output = vec;
    else
    current = maxrec(vec(1,1));
    next = maxrec(vec(1, 2:1:length(vec)));
    if current > next
    output = current;
    else
    output = next;
    end
    end
    end
     
  2. jcsd
  3. Nov 13, 2012 #2

    rcgldr

    User Avatar
    Homework Helper

    This is not a good case for using recursion. One way to do this would be to recursively split a vector in to sub-vectors of 1/2 the size in until vector size is 1 or 2. If size is 1, just return the single value, if size is 2, compare the two numbers and return the larger number.

    Factorial is commonly used as an example for recursion:

    Code (Text):

    unsigned int factorial(unsigned int n)
    {
        if(n == 0)
            return(1);
        else
            return(n * factorial(n-1));
    }
     
    What happens here is that each recursive call to factorial() pushes (n-1) and the return address onto the stack. Eventually when (n-1) == 0, that instance of factorial(0) returns a 1, then the previous (next higher) instance of factorial(1) returns a 1, then the previous instance of factorial(2) returns a 2, then the previous instance of factorial(3) returns a 6, ...

    If you have access to a source level debugger that also lets you look at the assembly code, memory (the stack) and registers, you can see what is going on.
     
    Last edited: Nov 14, 2012
  4. Nov 14, 2012 #3
    The idea behind recursion is a simple one. If you don't know the answer to the problem, make progress by making it smaller. When the problem is so small that you know the answer, supply the answer (this is the base case).

    In your maxvec example, the base case is: if the vector only has one element, then that element is the maximum element.

    The making the problem smaller is this: the maximum element of a non-trivial vector is the larger of its first element and the maximum of the rest of the vector. The maximum of the rest of the vector is found by calling maxrec again but with a vector that runs from element 2 to the end.
     
    Last edited: Nov 14, 2012
  5. Nov 14, 2012 #4

    rcgldr

    User Avatar
    Homework Helper

    Assuming this is matlab, doesn't vec(1,1) (two indexes being used) mean that vec is a matrix as opposed to a vector? So is vec a matrix with 1 row and multiple columns?

    I don't know if this will help, but here's a alternate binary splitting algorithm that I mentioned in my previous post, with vec as an array (vector) instead of a matrix. I'm not sure if my syntax is correct, but it should be close enough for you to get the idea:

    Code (Text):

    function output = maxrec(vec)
        lenvec = length(vec);
        if lenvec == 1
            output = vec(1);
        else
            lenvec2 = idivide(lenvec, 2);
            left = maxrec(vec(1:lenvec2));
            right = maxrec(vec(1+lenvec2:lenvec));
            if left > right
                output = left;
            else
                output = right;
            end
        end
    end
     
     
    Last edited: Nov 14, 2012
  6. Nov 14, 2012 #5
    Thanks for the response rcgldr and aralblec.

    Really the matrix (1, *insert something here*) is supposed to represent a vector, its the way out professor likes us to write it. Essentially it is a matrix with 1 row by m columns.

    I understand recursion but not in this form, something is confusing me. What I would like to know is exactly how it is looping around with some type of example, that's the only way I'll really understand this setup.

    EDIT: Okay so I ended up figuring it out by trying to explain why I don't understand it.. xD, Essentially I realized that the command *next = maxrec(vec(2:1:length(vec)));* increases the value of next after every iteration. I previously assumed that *next* value does not increase in recursion.

    To my understanding, this is what is going on in the program with a vector [2 3 1 5]

    Is length(vec)==1? no.

    current = 2 (index 1)
    next = 3 (index 2)

    is current > 2? no. perform else command
    output = next. next is now 1 (index 3), current stays the same

    now we loop back to command * next = maxrec(vec(2:1:length(vec))); *

    is current > next? 2 > 1? yes. loop back to current = maxrec(vec(1));

    current = 2 (index 1), next = 5 (index 4)

    is current > next? No. perform else command output = next. now we loop back to command * next = maxrec(vec(2:1:length(vec))); *

    next = 5 (index 4) it cannot increase anymore. therefore by output = next, output is thus = 5 (index 4) which gives us the maximum value in the vector.
     
    Last edited: Nov 14, 2012
  7. Nov 14, 2012 #6

    rcgldr

    User Avatar
    Homework Helper

    maxrec() continues to call itself until length of the recursively passed vec == 1. Then it returns back up the chain, returing the greater of that instance of current or next. There will be 3 "instances" of current, 3 "instances" of next, and 3 "instances" of vec stored on the stack during the recursions (plus the original instance of vec from the initial call). I used indentation to indicate the recursive calls.

    Code (Text):

    maxrec[2 3 1 5]   (initial call to maxrec)
      length([2 3 1 5]) != 1, current = [2 3 1 5](1) = 2, next = maxrec([3 1 5])
        length([3 1 5]) != 1, current = [3 1 5](1) = 3, next = maxrec([1 5])
          length([1 5]) != 1, current = [1 5](1) = 1, next = maxrec([5])
            length([5]) == 1, return [5]
          next = [5]
          if( current (=[1]) > next (=[5]) ) ... return [5]
        next = [5]
        if( current (=[3]) > next (=[5]) ) ... return [5]
      next = [5]
      if( current (=[2]) > next (=[5]) ) ... return [5]
    output = [5]
     
     
    Last edited: Nov 14, 2012
  8. Nov 14, 2012 #7
    Code (Text):

    function call to maxrec [2 3 1 5]
    is length(vec) == 1? No. current = maxrec(2). next = maxrec(3 1 5).
    What makes it loop back here? I would really like to know what the program is thinking, what is making it loop here? When it sees maxrec?

    So say it sees current = maxrec(2). So it loops back and calls the the original function and calculates from the beginning, but it will keep doing that ad infinitum before it reaches line [6].

    Oh, I thought it was looping at line [7] and [9]

    The way I interpreted it is that it never loops back to
    Code (Text):
    if length(vec) == 1
    output = vec;
    I also interpreted maxrec(vec(2:1:length(vec))) to mean start at index 2, after every loop *from recursion* you will go to the next index. But now I see that that is a blatant mistake.

    *misinterpretation shown below*

    Code (Text):
    maxrec[2 3 1 5]   (initial call to maxrec)

    is length(vec) == 1? No.

       current = 2. next = 3. is 2>3? No. Output = 2 = next *loops back to line [6]*
            next = 1. Is 2>1? Yes. Output = 1 = current *loop back to line [5]*
               current = 2. next = 5. Is 2>5? No. output = next *can not increase by 1 any longer, therefore the program ends*

    output = 5

     
     
  9. Nov 14, 2012 #8

    rcgldr

    User Avatar
    Homework Helper

    There isn't a maxrec(2) call being done. Current is just set to the first element of vec:
    Code (Text):

    function call to maxrec [2 3 1 5]
    is length(vec) == 1? No. current = (2). next = maxrec(3 1 5).
     
    You could think of the recursion as having multiple copies of the maxrec() function. The statement next = maxrec(3 1 5) is calling maxrec again, but it's a different instance of maxrec. This happens again with next = maxrec(1 5), and again with next = maxrec(5). Only then does maxrec return back to the previous instance of maxrec, storing the output in next and continuing from that line of code, then returning back again, and again ...

    It's like this (the calls are nested (resursion)):

    next = maxrec(3 1 5){ ... next = maxrec(1 5){ ... next = maxrec(5){ ... output 5 } ... output 5 } ... output 5 }

    with different data (8 5 3):

    next = maxrec(8 5 3){current = 8, next = maxrec(5 3){current = 5 next = maxrec(3){... output 3 }... output 5 }... output 8 }


    Take a look at my previous post again and see if that makes sense now.

    Assuming this is matlab code, do you have a copy of matlab and does it have a source level debugger? If so, you can write up this code, then use the debugger to see what's happening.
     
    Last edited: Nov 14, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook