Could someone explain how this code works?

So, we were given this as an example of recursion. It's a program that computes the factorial of a given scalar.

function f = factorial(x)
temp = 0;
if (x == 1)
    temp = 1;
else
    temp = x*factorial(x-1);
end

I get that x is inputted and if it's value is 0, then it returns 1 right off the bat. However, if x is not equal to 1 then the operation temp = x * factorial(x - 1); is carried out. So, x - 1 is then passed to factorial(), this is where I'm lost. What happens now? How does the value of temp not end up as 0, seeing as it's reset to that at the beginning of the function? Also, how does the code know when to stop and return the result?

f = temp;

Answer 1

[Cedric]

The line

 temp = 0 ;

is useless, and the temp which appear afterwards should be f, the output argument.

Hint: consider all "instances" of the factorial function as different, and draw a schematics, e.g.

 x = factorial(3)
     -> factorial, x=3  [1st instance]
        |   ..
        |   else
        |      f = x * factorial(3-1)      
        |              ->       factorial, x=2  [2nd instance]
        |                       |   ..
        |                       |   else
        |                       |      f = x * factorial(2-1)
        |                       |              ->       factorial, x=1  [3rd in.]
        |                       |                       |   if x == 1
        |                       |                       |      f = 1 ;
        |                       |              <- 
        |                       |      so f = 2 * 1
        |              <-                    
        |      so f = 3 * 2

 so x = 6

EDIT: I just realized that there was a typo that you spotted!

This was not

 factorial(3 - 2)

but

 factorial(3 - 1)

Thank you, I made the correction.

[David]

Am I reading that from top left to bottom right then to bottom left? Where did factorial(3 - 2) come from?

[Youssef Khmou]

yes from top left, or you can use :

 f=prod(1:N);

[Cedric]

Yes, and you follow the arrows. What people usually don't understand about recursive functions is that each call generates a new .. let's call it "instance" of the function, which has its own local context. In other words, this means that the x and f from the second instance are not the same as x and f from the first instance. They are elsewhere in memory and unrelated.

So the line

 x = factorial(3)

creates instance 1 with its own local context (where x equals 3) and the code of the function is executed. It reaches the line

 f = x * factorial(x-1)

evaluates x-1, which is 3-1=2 and calls factorial passing this 2 as input argument. This creates the 2nd instance of the function with its own local context where x equals 2. The code of this second instance is executed until it reaches the line

 f = x * factorial(x-1)

x-1 is evaluated, which gives 2-1=1 and factorial is called with this 1 as input argument. This creates the 3rd instance of the function with its own local context where x equals 1. The code of this third instance is executed. As x equals 1, the condition of the IF statement is true and the line

 f = 1 ;

is executed. Note that it is the f of the third instance which is deinfed, and at this point neither the f of the second instance nor the f of the first instance are defined. The end of the third instance is reached, which outputs the value of f (1) in the expression

 f = x * factorial(x-1)

of the second instance. At this point the third instance doesn't exist anymore (context/local variables destroyed/freed), the program is back in the second instance and can now compute f based on the 1 returned by the third instance and the value of x which is 2, so f=2*1=2. This defines f in the second instance. Note that at this point f from the first instance is not defined yet. The program goes on, hits the end of the second instance, which defines its output with the value of f (2). We are back in the first instance and the second instance is destroyed. The line

 f = x * factorial(x-1)

can be evaluated with the output of the second instance (2) and the value of x from the first instance (3). This defines f in the first instance: f=3*2. The program goes on and hits the end statement. This defines the output of the first instance with the value of f (6). We are now back in the main/base context, where this output defines the value of variable x.

[Youssef Khmou]

great explanation Cedric

[Cedric]

Thanks. Now I'll put ice on my fingers!

[David]

That's a brilliant explanation. Completely get it now. Thank you!

[Cedric]

You're welcome!

Answer 2

[Youssef Khmou]

David, The variable temp is local (inside the function), as long as the iterative variable x didnt arrive at 1 the process continues, "temp" is set only inside function , N=4 :

          inside func               insde func
N=4 -> (Temp=0,..,Temp=3)-->N=3 (Temp=0,Temp=2) .....N=1

[David]

Think I've got it now. So the value of factorial(x - 1) is calculated and multiplied by x and calculated again over and over again until x == 1? Temp is specific to each iteration of factorial()? Thanks!

[Youssef Khmou]

correct