Recursion or Looping

Question

I have this method that calculates some statistics:

public void calculateAverage(int hour){

    if (hour != 20) {
        int data =0; 
        int times = 0;
        for (CallQueue cq : queues) {
            data += cq.getCallsByTime().get(hour);
            times++;
        }       
        averageData.add((double)data/times);
        calculateAverage(hour + 1);
    }
    
}

Now I am very proud that I have created a recursive method but I know that this could have been solved with a loop.

My question is: is it better to solve these kind of problems recursive or with a loop?

recursion is considered to be the more "elegant" solution to iteration. — mre, Nov 12 '12 at 15:24
What happens when you call `calculateAverage` with hour > 20 e.g. 21? — Yogendra Singh, Nov 12 '12 at 15:25
This isn't even a recursive function, it's just a recursive **procedure**. It doesn't use recursion to any real effect. And yes, in Java recursion is never the first choice because it is not a tail-call-optimized language, so you're stressing the call stack unnecessarily. — Marko Topolnik, Nov 12 '12 at 15:26
Does this answer your question? [Recursion or iteration?](https://stackoverflow.com/questions/478570/recursion-or-iteration) — niamulbengali, Dec 14 '20 at 08:18

score 7 · Accepted Answer · edited Dec 14 '20 at 08:17

Recursion in general

In general, a recursion would be more expensive, because the stack has to be modified with copies of variables for each time the function recurses.

A set of addresses & states need to be saved, so that the recursive procedure can return to the right state after that particular run.

Iteration would be better if possible. Recursion, when iteration just won't cut it, or will result in a lot more complicated code.

Code Maintenance

From a maintenance perspective, debugging iterative code is a lot easier than recursive procedures as it is relatively easier to understand what the state is at any particular iteration, as compared to thinking about a particular recursion.

Your code

The procedure calls itself, but each run has nothing to do with the results of the previous run. Each run being independent, is usually the biggest give-away, that recursion there might not be necessary.

In my opinion, calculateAverage(hour + 1); should be moved outside the function, as it would also be clearer to someone reading your code. that each call is independent.

@giorashc they are much more complicated than recursion when the actual problem is better solved by recursion. Of course it is not the case here so iteration looks clearer. For instance, radix-2 FFT is easier to write and read using recursion than iteration. — Esailija, Nov 12 '12 at 15:29

score 2 · Answer 2 · edited May 23 '17 at 11:56

2

In Java, C, and Python, recursion is fairly expensive compared to iteration (in general) because it requires the allocation of a new stack frame. In some C compilers, one can use a compiler flag to eliminate this overhead, which transforms certain types of recursion (actually, certain types of tail calls) into jumps instead of function calls. (source)

edited May 23 '17 at 11:56

Community

1
1

answered Nov 12 '12 at 15:29

dreamcrash

47,137
25
94
117

score 1 · Answer 3 · answered Nov 12 '12 at 15:27

For this particular problem there isn't too much of a runtime difference. I personally would rather use iteration, I think it would be more simple and easier to understand, but to each his own I suppose.

now some recursive functions(like recursive Fibonacci numbers for example) should be done by iteration instead, simply because they can have exponential growth.

generally, I don't use recursion unless It would make my problem actually easier to understand.

score 1 · Answer 4 · answered Nov 12 '12 at 15:27

You should investigate the perimeter circumstances. For big recursions stack might get overflow, thats +1 for loops.

I'm not sure which one runs faster but that is relatively easy to measure, taking JIT and other stuff into considerations.

Code maintenance aspect: it is much easier for the most of us to understand and fix loops than recursion. Developers time is usually more important than minor performance differences.

score 1 · Answer 5 · answered Nov 12 '12 at 15:28

It depends on the context. For example if I have a tree of Composite objects (in SWT) and you wish to traverse them the easiest way is to use recursion like this:

    private boolean checkControlParent(Composite comp) {
        boolean ret = false;
        if (comp != null) {
            if (this.equals(comp)) {
                ret = true;
            } else {
                ret = checkControlParent(comp.getParent());
            }
        }
        return ret;
    }

otherwise if performance is important be advised that recursive calls are slower in most cases than simple loops because of the function/method call overhead.

So the main thing is that if you need to iterate through objects where recursion is a natural solution and you don't risk a StackOverflowError go ahead and use recursion. Otherwise you'll probably better off with a loop.

One more thing: recursive methods are sometimes tend to be harder to read, understand and debug.

Recursion or Looping

5 Answers5

Recursion in general

Code Maintenance

Your code

Linked