Recursive factorial

1

Trying to do the factorial recursively in Javascript, I get 2 different errors, why does this happen? and how should it be done? ( According to my code )

/* 1ra forma */

function f1(n){ // Maximum call stack size exceeded
  if(n < 1) return n;
  else return f1(n * (n-1));
}


/* 2da forma */

function f2(n,neutro=1){ // Devuelve 1
 if(isNaN(n)) n = parseInt(n,10);
 if(n < 1) {return neutro;}
 else {
 neutro *= n;
 return f2(n-1)
 }
}
    
asked by Eduardo Sebastian 23.10.2017 в 18:56
source

5 answers

2

In the first function, what happens is that the stop condition is not met and enters an infinite loop, that's why you get the error:

Maximum call stack size exceeded

This happens because you recursively call the function in the following way:

return f1(n * (n-1));

Doing this does not decrease the value of the input parameter of the function as expected, but increases so it never ends.

For example:

Si n = 3 

f1(3){
  if(3<1){
    return n; //no se cumple
  }else{
   return f1(3 * (3-1)); //f1(3 * (2)) regresa 6 
  }
}

In such a way that the stop condition is never met.

To correct this problem send as input parameter only the decreasing value to your function, since that is what the factorial is about. In code it would be something like this:

function f1(n){
  if(n === 1) 
    return 1;
  else 
    return n * f1((n-1));
}
    
answered by 23.10.2017 / 19:49
source
2

Your factorial function should be at least similar to this:

function f1(n){
    if(n < 2) return 1;
    else
        return n*f1(n-1);
}

f1(5);

In this way you are making them multiply decreasingly from the number passed and ending when it reaches 1 since at the end the factorial of 0 and 1 is 1, in this way the calculation would be 5 * 4 * 3 * 2 * 1, if you put

return f1(n*(n-1));

enters an endless recursion since it will never n reach the stop value, but will increase in each execution.

    
answered by 23.10.2017 в 19:32
1

In the first example, you do not actually return the same value if it is less than 1, it must actually be the same or have a value of 0:

function f1(n){
  //if(n < 1)
  if (n == 0 || n == 1)
     return n;
  else 
   return f1(n-1) * n
}

alert("Factorial de 4 es: " + f1(4));

In your example 2, the same thing but you must also multiply by n the result of the function using n-1 as a parameter:

    function f2(n,neutro=1){ // Devuelve 1
     if(isNaN(n)) n = parseInt(n,10);
    if (n == 0 || n == 1){
        return n;
     //if (n < 1) {
     //  return neutro;
     } else {
     //neutro *= n;
     return f2(n-1) * n
     }
    }
    
      alert("Factorial de 4 es: " + f2(4));

Here you can find a better optimized option , made by @Marguz

var f = [];
function factorial (n) {
  if (n == 0 || n == 1)
    return 1;
  if (f[n] > 0)
    return f[n];
  return f[n] = factorial(n-1) * n;
} 

 alert("Factorial de 100 es: " + factorial(100));
    
answered by 23.10.2017 в 19:12
1

The first case gives you an error Maximum call stack size exceeded because the function never stops calling this is because you subtract -1 an but multiply it by n then the value of n is in an exponential increase so it will never enter the if and therefore stay in an infinite cycle.

In the second it gives you a one because you are returning the neutral that equals it to 1 each that is called the function

    
answered by 23.10.2017 в 19:44
1

I think you should try using the iterative factorial. That saves you from having to run into problems like this. The code would be:

function factorial(n) {

  var res = 1;
  
  for (let i = 2; i <= n; i += 1) {
    res *= i;
  }
  
  return res;

}
    
answered by 23.10.2017 в 22:02