-1

I've implemented two Java codes for calculating the factorial of a number, one using recursion and the other using iteration. The iterative code seems to be faster than the recursive code in terms of execution time. However, I'm curious to understand why this performance difference occurs.

Recursive Factorial Code:

public class RecursiveFactorial {

    public static long factorial(int n) {
        if (n == 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }

    public static void main(String[] args) {
        int number = 5;

        long startTime = System.nanoTime();

        long result = factorial(number);
        System.out.println("Factorial of " + number + " is: " + result);

        long endTime = System.nanoTime();
        double executionTime = (endTime - startTime) / 1_000_000_000.0;
        System.out.println("Execution time: " + executionTime + " seconds");
    }
}

time: 0.0138802 seconds Iterative Factorial Code:

public class IterativeFactorial {

    public static long factorial(int n) {
        long result = 1;

        for (int i = 1; i <= n; i++) {
            result *= i;
        }

        return result;
    }

    public static void main(String[] args) {
        int number = 5;

        long startTime = System.nanoTime();

        long result = factorial(number);
        System.out.println("Factorial of " + number + " is: " + result);

        long endTime = System.nanoTime();
        double executionTime = (endTime - startTime) / 1_000_000_000.0;
        System.out.println("Execution time: " + executionTime + " seconds");
    }
}

time: 0.0003859 seconds I would appreciate if someone could shed light on the reasons behind the observed performance difference between the recursive and iterative implementations. Additionally, it would be interesting to see some random execution times for both codes to further illustrate the disparity.

zoldxk
  • 2,632
  • 1
  • 7
  • 29
  • 1
    Every stack call brings some overhead, which is in the long run slower – fnymmm Jul 06 '23 at 13:13
  • 2
    Nice to read: [How do I write a correct micro-benchmark in Java?](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) – jhamon Jul 06 '23 at 13:29
  • 2
    Many, many issues here: [1] CPUs are incredibly complicated, 'why this faster than that' requires about 500 pages of detail. This is not an appropriate question for SO, other than: CPUs aren't understandable at the level you think they are understandable at. They don't 'run one instruction per cycle', for example. [2] This isn't how you build a benchmark. CPUs are complicated. So are JVMs. You can't just time them like this. Use JMH - see jhamon's link. [3] For java _specifically_, recursion is slower than in other languages because java doesn't do tail call optimization (for good reasons). – rzwitserloot Jul 06 '23 at 13:38
  • I tried with number=20 (the largest result that matches within a long). Placing the endtime before the println for a more accurate duration, I got few microseconds for both solutions. The iterative one usually slightly slower than the recursive solution but not 35 times as in your case. – Robert Kock Jul 06 '23 at 13:42
  • @rzwitserloot In this case TCO wouldn't be possible anyway, since the call isn't in tail position. The multiplication is the last operation. – David Conrad Jul 06 '23 at 13:52

1 Answers1

1

Short Answer: An iteration does not use the stack so it's faster than recursion.

Description: In recursion method get in memory every-time it is called. If an logic calls a method 90 times recursively then same method will get load into memory stack 90 times with repeated variables. Where loop/iteration get load into memory stack only once (when its method will get load) and most of variables will be reused.

Please refer: is-recursion-ever-faster-than-looping

Rishabh Kabra
  • 55
  • 7