CODEWITHSUNDEEP
javaloopsrecursionoptimizationdo-while
Oscar Jara
Oscar Jara

Reputation: 14187

Which is faster in Java, while or using recursive method?

I have the following sample class with these two methods:

Process.java:

public class Process {

    public Process() {
    }

    public static void countRecursive(int num) {
        System.out.println("countRecursive: " + num++);
        if (num <= 10) countRecursive(num);
        else return;
    }

    public static void countWhile(int num) {
        do System.out.println("countWhile: " + num++);
        while (num <= 10);
    }

}

Main class:

public static void main(String[] args) {        

    Process.countRecursive(0);
    Process.countWhile(0);

}

Output:

countRecursive: 0
countRecursive: 1
countRecursive: 2
countRecursive: 3
countRecursive: 4
countRecursive: 5
countRecursive: 6
countRecursive: 7
countRecursive: 8
countRecursive: 9
countRecursive: 10

countWhile: 0
countWhile: 1
countWhile: 2
countWhile: 3
countWhile: 4
countWhile: 5
countWhile: 6
countWhile: 7
countWhile: 8
countWhile: 9
countWhile: 10

But I want to know which "technique" is recommended to use and why.

Thanks in advance.

Upvotes: 18

Views: 6273

Answers (8)

Adam Arold
Adam Arold

Reputation: 30528

Recursion will be slower because of the method call overhead and call stack usage.

Java isn't performing tail call optimization either so don't count on it. (Although there are languages on the JVM which do have tail call optimization including Clojure and Kotlin)

Another drawback might be the risk of a StackOverflowError in case you are filling up the stack.

If you are doing this just to try things out I suggest using VisualVM which can be found in the java JDK. It is a profiler which can be used to benchmark this kind of situation (or you can ask for an open source YourKit license if you're working on OSS).

Please note that I do not recommend using recursion just to be fancy. Use it if you really need it (traversing trees for example).

Upvotes: 36

D&#243;nal
D&#243;nal

Reputation: 187529

In general, I favour iteration (e.g. a while or for loop) over recursion because:

  • Iteration is simpler
  • If you recurse too deeply, you can get a stackoverflow exception. This cannot happen with iteration.

Upvotes: 6

Kevin
Kevin

Reputation: 15974

What everyone else said is true. I'd like to add one more thing: For the problem you posted, counting 1 to 10, using recursion or iteration will be fine either way because they both take a negligible amount of time to run. In general, on modern computer systems, you don't need to worry too much about how long a process will take to complete (unless you're dealing with large data sets) because memory is so cheap and CPUs are so powerful.

Usually, you write a program however you feel the most comfortable first, using good programming practices. If it takes too long to run after that, you optimize it then.

Not that looking into how iteration and recursion compare at this level is a bad thing. Again, iteration is usually preferable to recursion. My point is the lesson to learn is that while there are ways to make your code run quickly, you often don't need to worry about them when you're working with small data sets :)

Upvotes: 3

Marcin Szymczak
Marcin Szymczak

Reputation: 11433

You should run code with time measurement. Here you have my output for 100 recursions/ 100 while loops: 

Recursive time: 90941
While time: 5180

This clearly shows that while loop is faster than recursion.

You can check my measurements by running this code:

public class Process {

    public Process() {
    }

    public static void countRecursive(int num) {
        num++;
        if (num <= 100) countRecursive(num);
        else return;
    }

    public static void countWhile(int num) {
        do
            num++;
        while (num <= 100);
    }

    public static void main(String[] args) {
        Long start = System.nanoTime();        
        Process.countRecursive(0);
        System.out.println("Recursive time: " + (System.nanoTime() - start));
        Long startWhile = System.nanoTime();
        Process.countWhile(0);
        System.out.println("While time: " + (System.nanoTime() - startWhile));

    }

}

Upvotes: 11

Rohit Jain
Rohit Jain

Reputation: 213263

I would not suggest using Recursion, as each recursion is stored on stack. So, you need to store method parameters, local variables, etc, for each recursive call, to maintain the state of method before that call.

Also, you should obviously not go with recursion with this kind of problem. It should be left for some specific task, only when you really can't avoid using them.

Further, you can also benchmark your code to see which one runs faster. You will get an idea.

Upvotes: 10

Chris
Chris

Reputation: 4083

In general, recursion is optimized to loops if possible, meaning that for various reasons, including stack frame allocation and stack frame overflows iteration is favorable over recursion if the two solutions are otherwise equal. See Tail Recursion
So ignoring the fact that Java doesn't optimize Tail Recursion, loops should be faster.

Also take a look at this

Upvotes: 6

Slartibartfast
Slartibartfast

Reputation: 1623

Recursive calls add stack frames to the call stack. Loops do not. Loops are generally faster than recursion, unless the recursion is part of an algorithm like divide and conquer (which your example is not).

You should be able to time the execution of each of your methods and find out how much faster one is than the other.

Upvotes: 7

Rahul Tripathi
Rahul Tripathi

Reputation: 172448

In java, recursion is little expensive compared to while loop because it requires the allocation of a new stack frame. Recursion may well be faster where the alternative is to explicitly manage a stack

Upvotes: 5

Related Questions