JavaScript Recursive Functions

4

Someone could ask me a question!

function recursiveFatorial(x){
if (x == 0)
    return 1;
else
    return x * recursiveFatorial(x-1);
}


console.log("Resultado da funcao recursiveFatorial: ",recursiveFatorial(10));

/*
Output
10! 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 =  3628800
*/
  • First time the code runs, the value of X = 10 and the result of the expression return 10 * recursiveFatorial(10-1); will equal 3628800
  • Second time X = 9 return 9 * recursiveFatorial (9-1); = 40320
  • Third time X = 8 return 8 * recursiveFatorial (8-1); = 5040
  • 4x, 5x, 6x ... and so on, my question is:

When you finish running the code in 9x (or when index X is = 1) the result that the expression - > [return 1 * recursiveFatorial (1-1); ] will return has the value of 1, the next time the code rolls X will have the value of 0! Then the condition (x == 0) will be true and return 1; and not the result being printed on the 3628800 console!

I would like to know where 3628800 is being "stored"!

I do not know if I could explain it right! Anyway if anyone can help me understand how the console is emitting this value I will be very grateful.

    
asked by anonymous 05.05.2017 / 04:52

2 answers

4

To facilitate the response, let's take the 5 factorial as an example.

var resultado = recursiveFatorial(5); // 120

The variable resultado will be allocated in memory and its value will be the return of the function.

   Endereço     Variável            Valor
+------------+-------------+----------------------+
|   0x0001   |  resultado  | recursiveFatorial(5) |
+------------+-------------+----------------------+

When executing the function, the return will be 5 * recursiveFatorial(4) , so first the interpreter allocates in memory a space to calculate the return of the recursiveFatorial(4) function before multiplying by 5, as if it were a temporary variable:

   Endereço     Variável            Valor
+------------+-------------+----------------------+
|   0x0001   |  resultado  | recursiveFatorial(5) |
+------------+-------------+----------------------+
|   0x0002   |  temp_4     | recursiveFatorial(4) |
+------------+-------------+----------------------+

Again, the return will be 4 * recursiveFatorial(3) and the interpreter will first need to check the value of recursiveFatorial(3) , allocating in memory a space for it:

   Endereço     Variável            Valor
+------------+-------------+----------------------+
|   0x0001   |  resultado  | recursiveFatorial(5) |
+------------+-------------+----------------------+
|   0x0002   |  temp_4     | recursiveFatorial(4) |
+------------+-------------+----------------------+
|   0x0003   |  temp_3     | recursiveFatorial(3) |
+------------+-------------+----------------------+

The same goes for 2:

   Endereço     Variável            Valor
+------------+-------------+----------------------+
|   0x0001   |  resultado  | recursiveFatorial(5) |
+------------+-------------+----------------------+
|   0x0002   |  temp_4     | recursiveFatorial(4) |
+------------+-------------+----------------------+
|   0x0003   |  temp_3     | recursiveFatorial(3) |
+------------+-------------+----------------------+
|   0x0004   |  temp_2     | recursiveFatorial(2) |
+------------+-------------+----------------------+

And the same for 1:

   Endereço     Variável            Valor
+------------+-------------+----------------------+
|   0x0001   |  resultado  | recursiveFatorial(5) |
+------------+-------------+----------------------+
|   0x0002   |  temp_4     | recursiveFatorial(4) |
+------------+-------------+----------------------+
|   0x0003   |  temp_3     | recursiveFatorial(3) |
+------------+-------------+----------------------+
|   0x0004   |  temp_2     | recursiveFatorial(2) |
+------------+-------------+----------------------+
|   0x0005   |  temp_1     | recursiveFatorial(1) |
+------------+-------------+----------------------+

Finally, the value of recursiveFatorial(1) will be 1 * recursiveFatorial(0) , so another memory space is required. However, this time, when analyzing its value, it will be 1, since it satisfies the condition x == 0 , returning 1.

   Endereço     Variável            Valor
+------------+-------------+----------------------+
|   0x0001   |  resultado  | recursiveFatorial(5) |
+------------+-------------+----------------------+
|   0x0002   |  temp_4     | recursiveFatorial(4) |
+------------+-------------+----------------------+
|   0x0003   |  temp_3     | recursiveFatorial(3) |
+------------+-------------+----------------------+
|   0x0004   |  temp_2     | recursiveFatorial(2) |
+------------+-------------+----------------------+
|   0x0005   |  temp_1     | recursiveFatorial(1) |
+------------+-------------+----------------------+
|   0x0006   |  temp_0     | 1                    |
+------------+-------------+----------------------+

Once this is done, the interpreter replaces the returns of the functions with their values:

Value of recursiveFatorial(1) :

   Endereço     Variável            Valor
+------------+-------------+----------------------+
|   0x0001   |  resultado  | recursiveFatorial(5) |
+------------+-------------+----------------------+
|   0x0002   |  temp_4     | recursiveFatorial(4) |
+------------+-------------+----------------------+
|   0x0003   |  temp_3     | recursiveFatorial(3) |
+------------+-------------+----------------------+
|   0x0004   |  temp_2     | recursiveFatorial(2) |
+------------+-------------+----------------------+
|   0x0005   |  temp_1     | 1 * temp_0 = 1       |
+------------+-------------+----------------------+
|   0x0006   |  temp_0     | 1                    |
+------------+-------------+----------------------+

Value of recursiveFatorial(2) :

   Endereço     Variável            Valor
+------------+-------------+----------------------+
|   0x0001   |  resultado  | recursiveFatorial(5) |
+------------+-------------+----------------------+
|   0x0002   |  temp_4     | recursiveFatorial(4) |
+------------+-------------+----------------------+
|   0x0003   |  temp_3     | recursiveFatorial(3) |
+------------+-------------+----------------------+
|   0x0004   |  temp_2     | 2 * temp_1 = 2       |
+------------+-------------+----------------------+
|   0x0005   |  temp_1     | 1 * temp_0 = 1       |
+------------+-------------+----------------------+
|   0x0006   |  temp_0     | 1                    |
+------------+-------------+----------------------+

Value of recursiveFatorial(3) :

   Endereço     Variável            Valor
+------------+-------------+----------------------+
|   0x0001   |  resultado  | recursiveFatorial(5) |
+------------+-------------+----------------------+
|   0x0002   |  temp_4     | recursiveFatorial(4) |
+------------+-------------+----------------------+
|   0x0003   |  temp_3     | 3 * temp_2 = 6       |
+------------+-------------+----------------------+
|   0x0004   |  temp_2     | 2 * temp_1 = 2       |
+------------+-------------+----------------------+
|   0x0005   |  temp_1     | 1 * temp_0 = 1       |
+------------+-------------+----------------------+
|   0x0006   |  temp_0     | 1                    |
+------------+-------------+----------------------+

Value of recursiveFatorial(4) :

   Endereço     Variável            Valor
+------------+-------------+----------------------+
|   0x0001   |  resultado  | recursiveFatorial(5) |
+------------+-------------+----------------------+
|   0x0002   |  temp_4     | 4 * temp_3 = 24      |
+------------+-------------+----------------------+
|   0x0003   |  temp_3     | 3 * temp_2 = 6       |
+------------+-------------+----------------------+
|   0x0004   |  temp_2     | 2 * temp_1 = 2       |
+------------+-------------+----------------------+
|   0x0005   |  temp_1     | 1 * temp_0 = 1       |
+------------+-------------+----------------------+
|   0x0006   |  temp_0     | 1                    |
+------------+-------------+----------------------+

Finally, value of recursiveFatorial(5) :

   Endereço     Variável            Valor
+------------+-------------+----------------------+
|   0x0001   |  resultado  | 5 * temp_4 = 120     |
+------------+-------------+----------------------+
|   0x0002   |  temp_4     | 4 * temp_3 = 24      |
+------------+-------------+----------------------+
|   0x0003   |  temp_3     | 3 * temp_2 = 6       |
+------------+-------------+----------------------+
|   0x0004   |  temp_2     | 2 * temp_1 = 2       |
+------------+-------------+----------------------+
|   0x0005   |  temp_1     | 1 * temp_0 = 1       |
+------------+-------------+----------------------+
|   0x0006   |  temp_0     | 1                    |
+------------+-------------+----------------------+

Therefore, the value of the variable will be 120.

  

It was not the purpose of the answer to describe exactly the operation of the JavaScript interpreter, but rather to describe the basic operation of recursion, given the context given in the question, in which the author wants to know why the variable is not worth 1 if < in> seemingly this is the last return that occurs in the code.

    
05.05.2017 / 05:15
0

Within the recursiveFatorial method it calls the method itself (recursion) by passing the value of x - 1, until the value of x is equal to 0, so, as you passed the number 10, the console generated 10x9x8 x 7 x 6 x 5 x 4 x 3 x 2 x 1, if it had passed 20 would be: 20 x 19 x 18 x 17 ... 1

    
05.05.2017 / 04:59