Could someone explain how this code works?

Question

David 2013-10-10

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/89836-could-someone-explain-how-this-code-works

评论： Cedric 2013-10-12

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;

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Cedric 2013-10-10

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/89836-could-someone-explain-how-this-code-works#answer_99274

编辑：Cedric 2013-10-11

在 MATLAB Online 中打开

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.

7 个评论
显示 5更早的评论隐藏 5更早的评论

Cedric 2013-10-10

编辑：Cedric 2013-10-11

在 MATLAB Online 中打开

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.

David 2013-10-12

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

Cedric 2013-10-12

You're welcome!

请先登录，再进行评论。

Answer 2

Youssef Khmou 2013-10-10

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/89836-could-someone-explain-how-this-code-works#answer_99271

在 MATLAB Online 中打开

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

2 个评论
显示无隐藏无

David 2013-10-10

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 2013-10-10