Iterative or Recursive Factorial

Question

I've implemented factorial recursively this way:

int factorial(int x){
    if (x <= 0)
        return 1;
    else
        return (x*factorial(x - 1));
}

int _tmain(int argc, _TCHAR* argv[])
{
    std::cout << "Please enter your number :::";
    int x;
    std::cin >> x;
    std::cout<<"factorial(" << x << ") = "<< factorial(x);
    getchar(); getchar();
}

which way of implementing such code is more useful writing it using iteration and loops or writing it recursively such as above?

In general, if you can do without recursion and use an iterative algorithm you should. Not so much with something this simple, but debugging a recursive algorithm can be a real pain. The fun issue is what happens to the memory, particularly the stack, for instance think about what would happen if you called your function with an argument of say 30. PS Don't go much bigger, factorial goes over maxint quick. — Tony Hopkinson, Jan 28 '15 at 12:02
Because of the little range of factorial which fit in an int. I would simply use an array off all precalculated values. — MrSmith42, Jan 28 '15 at 12:09
Useful for what? Both ways are useful for teaching beginners about recursive and iterative programming. — sashoalm, Jan 28 '15 at 12:18
Perhaps it was better if had written 'Optimal' instead of 'useful'. — Mohamadreza, Jan 28 '15 at 12:33
Recursion is more "optimal" for generating large stacks easily. (Useful if you're making a debugger and testing its handling of stack-frames). Iteration is more "optimal" if you want the answer quickly with minimal memory. — abelenky, Jan 28 '15 at 12:36

nalinc · Accepted Answer · 2015-01-28T12:19:03.823

It depends on the number itself.

For normal-range numbers, recursive solution could be used. Since it makes use of previous values to calculate future values, it can provide the value of 'factorial(n-1)' on the fly.

factorial(n) = factorial(n-1) * n

However, since recursion makes use of stacks, it would eventually overflow if your calculation goes deeper than the stack-size. Moreover, recursive solution would give poor performance because of heavy push-pop of the registers in the ill level of each recursive call.

In such cases, iterative approach would be safe.

Have a look at this comparison.

Hope it helps!

score 1 · Answer 2 · edited May 23 '17 at 12:07

In C++ a recursive implementation is usually more expensive than an iterative one. The reason is that each call causes a creation of a new stack frame which holds data such as return address, local variables and registers that are needed to be saved. Therefore a recursive implementations requires amount of memory which is linear with the depth of your nested calls while iterative implementations use a constant amount of memory. In your specific case, which is tail recursion, a compiler optimization may switch the function call with a direct jump preventing the unnecessary usage of memory on the call-stack. For more detailed explanation you might want to read: Is recursion ever faster than looping?

Iterative or Recursive Factorial

2 Answers2