Recursive Functions in Javascript

Asked

Viewed 2,689 times

7

Could someone please clear me of a doubt !

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); shall be equal to 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 at 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 runs 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 wonder where is being "stored" that value 3628800!

I don’t know if I could explain it properly! Anyway if anyone can help me understand how the console is sending that amount I will be very grateful.

2 answers

7


To facilitate the response, take as an example the factorial of 5.

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 performing the function, the return will be 5 * recursiveFatorial(4), then first the interpreter allocates in memory a space to calculate the function return recursiveFatorial(4) 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 verify 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 happens 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), then another space in memory is necessary. However, this time, when analyzing its value, it will be 1, because 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 function returns with their due 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 how the Javascript interpreter works, but rather to describe the basic functioning of recursion, given the context given in the question, in which the author wishes to know why the variable is not worth 1 if apparently this is the last return that occurs in the code.

0

Within the recursive method it calls the method itself (recursiveness )passing the value of x - 1 until the value of x equals 0, so, as you passed the number 10, the console generated 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1, if you had passed 20 would be:20 x 19 x 18 x 17...1

Browser other questions tagged

You are not signed in. Login or sign up in order to post.