Yes, there is a more efficient solution that still uses recursion; specifically, using Tail Recursion.
When you return n * factorial(n-1);
, the compiler can’t optimize the call away because it still has more work to do when the call to factorial(n-1)
returns; it has to do the multiplication, and return the result.
If, instead, you ended the function with return factorial(arguments);
, the compiler can optimize away both the call and the return with a jump to the start of the factorial
function, with the new arguments. No additional stack frames are required. The arguments you need to pass would be the original argument(s) and any “running total”.
int factorial(int n, int product=1) {
if ( n <= 1 )
return product;
return factorial(n-1, n*product);
}
The difference between your implementation and a tail-recursive one can be seen by trying to calculate factorial(1000000000)
. Your implementation will require 1 billion stack frames, which should likely crash the program. A tail-recursive algorithm uses only 1 stack frame, so it will return the (incorrect) answer of zero.
(Why zero? Assuming 32-bit integer, 34! has 17 even numbers, 8 multiples of 4, 4 multiples of 8, 2 multiples of 16, and a 32, which means the answer is has 17+8+4+2+1=32 powers of 2. And any number multiplied by 2^32, modulo 32-bits is zero. Any higher factorial is a multiple of 34!, so will also evaluate as zero.)