Recursive factorial is suspiciously fast

Question

Recursive computation of a factorial should be slow due to high problem complexity. Why is not my basic implementation painfully slow? I am curious, since this should be textbook example of a bad approach.

Is it because some internal optimization or caching results in C# program?

using System;
using System.Diagnostics;
using System.Numerics;

namespace FactorialRecursion
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch stopwatch = new Stopwatch();
            for (int i = 0; i < 4000; i++)
            { 
                stopwatch.Reset();
                stopwatch.Start();
                Factorial(i);
                stopwatch.Stop();
                Console.WriteLine($"{i}! = ({stopwatch.Elapsed})");
            }
            Console.ReadKey();
        }

        static BigInteger Factorial(BigInteger number)
        {
            if (number <= 1)
                return 1;
            return number * Factorial(number - 1);
        }
    }
}

The results are here:

3990! = (00:00:00.0144319)
3991! = (00:00:00.0149198)
3992! = (00:00:00.0159502)
3993! = (00:00:00.0116784)
3994! = (00:00:00.0104608)
3995! = (00:00:00.0122931)
3996! = (00:00:00.0128695)
3997! = (00:00:00.0131792)
3998! = (00:00:00.0142510)
3999! = (00:00:00.0145544)

1) debug it, or 2) print out the value of the factoral and you can see for yourself. — , Sep 23 '16 at 20:37
For input N, you're doing N multiplication operations. Why wouldn't that be fast? — SlimsGhost, Sep 23 '16 at 20:39
"I am curious, since this should be textbook example of a bad approach." Did you maybe confuse it with fibonacci, where the very naive recursive version is O(2^n) time complexity? — AliciaBytes, Sep 23 '16 at 20:42
If you want to check that idea of caching results, try reversing your loop arguments: start at 4000 and work backward. If caching is the "culprit", you'll see a long time for the first case, 4000!, and trivial times for the others. — Prune, Sep 23 '16 at 23:48
@Prune: While caching is clearly not the issue in this question, that is a nice trick that you mentioned to find if caching is happening in the background. — displayName, Sep 27 '16 at 14:00

score 3 · Answer 1 · answered Sep 23 '16 at 20:38

3

The recursive approach in factorial calculation is considered bad because of stack memory consumption and not because of speed.

If you take a large enough number, you will quickly run out of memory to calculate the factorial and not that you will be slow (provided the memory where you are storing the factorialed value is large enough to store it).

answered Sep 23 '16 at 20:38

displayName

13,888
8
60
75

How is this answering the OPs question? – Sylwester Sep 23 '16 at 20:40
2

@Sylwester: OP is saying that recursive approach is considered bad, but (s)he doesn't know why. That's what this answer answers. The badness of recursive approach is in memory consumption, not speed. – displayName Sep 23 '16 at 20:41
Reread the question. OP doesn't understand why it's not worse than his measurments. OPs questions really are "Why is not my basic implementation painfully slow?" and "Is it because some internal optimization or caching results in C# program?". Which of those are this an answer to? – Sylwester Sep 23 '16 at 20:45
1

@Sylwester: OP has assumed that bad means slow (probably you too have). Bad, in the context of recursive factorial calculation, means having a O(n) memory consumption when it could be O(1) in iterative version. – displayName Sep 23 '16 at 20:48
2

@Sylwester the answer is that OPs assumptions are wrong and there is no time problem with the recursive version at all. Just maybe a space complexity issue with his naive version. – AliciaBytes Sep 23 '16 at 20:48
1

@displayName Just to nit, it's not `O(1)`. It's `O(N*log(N))`. The OP is using BigInteger. And the number of digits in `N!` is `O(N*log(N))`. So in the recursive case, it would on the order of `O(N^2*log(N))`. The run-time is also same. But `N = 4000` isn't a particularly large input for this quadratic algorithm. – Mysticial Sep 23 '16 at 20:52
Correction to my comment about the memory complexity being `O(N^2*log(N))`. The recursion doesn't keep a `BigInteger` at every stack frame. Only the bottom frame has it. So the memory usage is `O(N*log(N))`. But the time complexity is still `O(N^2*log(N))`. – Mysticial Sep 23 '16 at 20:56

score 2 · Answer 2 · answered Sep 23 '16 at 20:40

The time complexity of a factorial func using both recursion and iteration is the same,although recursion using extra memory space to store the function calls in the stack.But,as far as the time complexity is concerned,it's the same in this case because the recursion is acting indirectly as a loop..Time-complexity of recursion becomes worse than it's iterative counterpart,when recursion tries to calculate the same value again and again which is avoided in iteration.(ex:- Fibonacci num gen using recursion without memoization has O(2^n) worst-case time complexity,whereas it's iterative counterpart has O(n) worst-case time complexity.

score 0 · Answer 3 · edited May 23 '17 at 11:48

0

There is a chance that the JIT is using tail recursion optimizations which is helping to speed things along, see this for more information. It is hard to say for sure though without having access to your environment.

The given approach is considered the unfavorable one because it uses a lot of stack memory for processing larger factorials. It has less to do with speed and more to do with how much memory it consumes. However, if you know tail recursions are going to happen there (decided by the JIT, not by you so don't count on it), it really doesn't matter.

edited May 23 '17 at 11:48

Community

1
1

answered Sep 23 '16 at 20:42

Cody

2,643
2
10
24

Don't think so. C# doesn't have TCO and even if it did this particular code does not recurse in tail position. – Sylwester Sep 23 '16 at 20:47
According to that link, the C# compiler doesn't support tail recursion, however the JIT does, and you can more or less force it by using specific compiler options, otherwise it is up to the JIT. It made me think it was possible due to the last line being the recursive call, but its likely it isn't. Since I didn't know for sure, I thought I'd add it in with a disclaimer. – Cody Sep 23 '16 at 20:51

Recursive factorial is suspiciously fast

3 Answers3