How do recursions work exactly?

[Nano-Passion]

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

 

[rcgldr]

Find largest number in a vector using recursion.

This is not a good case for using recursion. One way to do this would be to recursively split a vector into 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:

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 let's you look at the assembly code, memory (the stack) and registers, you can see what is going on.

 

[aralbrec]

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.

 

[rcgldr]

current = maxrec(vec(1,1));

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:

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

 

[Nano-Passion]

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]

function output = maxrec(vec)

if length(vec) == 1
output = vec;
else
current = maxrec(vec(1));
next = maxrec(vec(2:1:length(vec)));
if current > next
output = current;
else
output = next;
end
end
end

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.

 

[rcgldr]

This is what is going on in the program with a vector [2 3 1 5]

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.

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]

 

[Nano-Passion]

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

[1] function output = maxrec(vec)
[2] if length(vec) == 1
[3]output = vec;
[4] else
[5] current = maxrec(vec(1));
[6]next = maxrec(vec(2:1:length(vec)));
[7]if current > next
[8]output = current;
[8]else
[9]output = next;[
[10] end
[11] end
[12] end

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

The way I interpreted it is that it never loops back to

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*

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

 

[rcgldr]

function call to maxrec [2 3 1 5]
is length(vec) == 1? No. current = maxrec(2). next = maxrec(3 1 5).

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

function call to maxrec [2 3 1 5]
is length(vec) == 1? No. current = (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?

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.