Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I was doing a basic problem on coding a factorial \$n!\$:

function factorialize(num) {
  if (num < 0) {
 return undefined;
  } else if (num === 0) {
    return 1;
  }
  else {
    return num * factorialize(num - 1);
  }
}

The site I'm learning from accepted this solution, but they're only testing for nonnegative integers, i.e for \$n \ge 0\$, not negative integers.

So I got curious on how to compute a negative factorial \$(-n)!\$. Many pages say it's undefined, but I found two saying it could be defined.

The gist I got is that:

\$|n!| = |(-n)!|\$

Their absolute values are the same but the negative factorials change signs.

Examples:

\$4! = (-4)! = 24\$

\$5! = 120\$ but \$(-5)! = -120\$

The formula that I gathered from the two linked pages is:

\$(-n)! = |n|! * (-1)^n\$

And this reflects my code. From test cases, I think I've nailed it. I just want to ask if there's a better way of coding it. Someone from here remarked that using recursion is memory-inefficient.

function factorialize(num) {
 if (num === 0) {
   return 1;
  } else if (num > 0) {
     return num * factorialize(num - 1);
  } else {
     return Math.pow(-1, num) * Math.abs(num) * factorialize(Math.abs(num) - 1);  
    }
  }

// test cases below
    console.log(factorialize(-1)); // -1
    console.log(factorialize(1)); // 1
    console.log(factorialize(0)); // 1
    console.log(factorialize(-2)); // 2
    console.log(factorialize(2)); // 2
    console.log(factorialize(-3)); // -6
    console.log(factorialize(3)); // 6
    console.log(factorialize(-4)); // 24
    console.log(factorialize(4)); // 24
    console.log(factorialize(-5)); // -120
    console.log(factorialize(5)); // 120
share|improve this question
1  
Cross-posted with SO – Mast 2 days ago
    
can't add a 4th link in main body of post so I'm posting it here * Edited to add Link 3: [link]: (springerplus.com/content/pdf/2193-1801-3-658.pdf) Factorials of real negative and imaginary numbers - A new perspective – elp1987 yesterday
up vote 2 down vote accepted

Changing your function to something like this would work. I don't think you need to model your function after the mathematical equation.

function factorial(num) {
  if (num < 0) {
    return num * factorial(num + 1);
  } else if (num == 0) {
    return 1;
  } else {
    return num * factorial(num - 1);
  }
}

Another solution that uses tail call optimization could be

function factorial(num) {
  function recur(n, acc) {
    if (n < 0) {
      return recur(n + 1, n * acc);
    } else if (n == 0) {
      return acc;
    } else {
      return recur(n - 1, n * acc);
    }
  }
  return recur(num, 1);
}
share|improve this answer
    
WOW. This is the best recursive solution so far! It's very elegant! THANK YOU. – elp1987 yesterday

Tail-call optimization

This is a problem line:

return num * factorialize(num - 1);

Every time this line is run, the execution of this function is "stopped" while the execution of this new factorialize function starts. Depending on how big num is, this could create a very large call stack and could even bring up some memory problems in your code.

What you need it tail-call optimization. Tail-call optimization is a form of optimization to remove this call-stack buildup in your code by slightly refactoring a function.

This is what your optimized function would now look like:

function factorialize(num, fac) {
    if(fac === undefined) { // for more clean function calling
        fac = 1;
    }

    if (num < 0) {
        return undefined;
    } else if (num === 0) {
        return fac;
    } else {
        return factorialize(num - 1, num * fac);
    }
}

Notice that last return line; it uses the new fac parameter to keep track of the value that it would normally be returning at this point. Now, instead of constantly building up on the stack, the factorialize will completely finish executing before the next function starts. This keeps the stack size constant.

Now, to call this new function, you would write:

factorialize(5);

to get the factorial of 5. Note that you don't need to specify the second paramter because of the first conditional in the function. Now, you can remove this conditional if you'd like, but you'd have to either:

  • Call the function with that "random" 1 argument.
  • Create a separate function for calling this function with the 1 argument. This function would only take the number to be factorialized. That would look like this:


function factorialize(num) {
    _factorialze(num, 1);
}

where _factorialze is the original function (the _ indicates that it should not be directly called).

share|improve this answer
    
Good catch about tail call optimization. This is an important point. – Sandro yesterday
    
I think both your and @Sandro's solutions are good. You explain tail-call optimization well for beginners, but I think the if (fac === undefined) fac = 1 is a bit ugly. Could you perhaps change it so that you make another function that calls factorialize with 1 as the second argument? – gardenhead yesterday
1  
@gardenhead Done! However, instead of completely replacing it, I appended the code onto the bottom. – SirPython 22 hours ago

factorialize() is a strange function name, I would change that simply to factorial().

In your recursive function,

return Math.pow(-1, num) * Math.abs(num) * factorial(Math.abs(num) - 1);

can be simplified to

return Math.pow(-1, num) * factorial(Math.abs(num));

I assume that Math.pow is fast when computing an integer power of -1, but if you want to avoid it, you can compute the factorial by recursing to factorial(num - 1) or factorial(num + 1), depending on the sign of num:

function factorial(num) {
    if (num === 0) {
        return 1;
    } else if (Math.abs(num) == 1) {
        return num;
    } else if (num > 0) {
        return num * factorial(num - 1);
    } else {
        return num * factorial(num + 1);
    }
}

The iterative version is even shorter and simpler:

function factorial(num) {
    var result = 1;
    var sign = Math.sign(num);
    for (var i = num; i !== 0 ; i -= sign) {
        result *= i;
    }
    return result;
}

Starting with num, all factors towards (but excluding) zero are multiplied.

share|improve this answer

The non-recursive way:

function factorialize_no_recursion(num, sign, originalNum) {
   sign = sign || 1;
   originalNum = originalNum || num;
   var ret = 1;
   var increment = (originalNum >= 0) ? -1: +1; 

   while (true) {
      if (num === 0) 
         return ret;

     if (num > 0) 
        ret *= num * (originalNum >= 0 ? sign : -sign);
     else
        ret *= -sign * Math.abs(num);  

     num += increment;
   }     
};

Using recursion requires some extra space on stack (at least on languages like C# or Java, I am not familiar with memory model in JS), but what is more important is reaching max recursion depth - see here for details.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.