Are recursive methods always better than iterative methods in Java?

Question

Are recursive methods always better than iterative methods in Java?

Also can they always be used in place of iteration and vice-versa?

Answer 1

Are recursive methods always better than iterative methods in java?

No

Also can they always be used in place of iteration and vice-versa?

You can always make an iterative function from a recursive one (if memory can handle it, see interesting link here).

For some cases, it's better to use recursion (like when dealing with trees.. traveling on a binary tree, etc.). For me, if using loops isn't more complicated and much more difficult than a recursion, I prefer to use loops.

Recursion uses more memory but is sometimes clearer and more readable. Using loops increases the performance, but recursion can sometimes be better for the programmer (and their performance).

So, for the conclusion, deciding what to use - recursion or iteration, depends on what you want to implement, and what's more important for you (readability, performance...), and asking recursion or iteration is like asking for elegance or performance.

---

Example

Consider these two implementation for the factorial:

Iterative:

private int Factorial(int num)
{
    int result = 1;
    if (num <= 1) 
       return result;
    while (num > 1)
    {
        result * = num;
        num--;
    }
    return result;
}

Recursion:

private int Factorial(int num)
{
    if (num <= 1) 
        return 1;
    return num * Factorial(num - 1);
}

Which method is more readable?

Obviously the recursive one, it is straight forward and can be written and successfully run from the first try - It is simply translating math definition into Java!

Which method is more efficient?

Take for example num = 40, here is a time comparison:

long start = System.nanoTime();
int res = Factorial(40);
long end = System.nanoTime();
long elapsed = end - start;
        
System.out.println("Time: " + elapsed); 

2993 for the recursive

2138 for the iterative

of course, the difference will be larger when num is larger.

Answer 2

Recursion is good for programmers to understand a program, but many times they cause stackoverflows hence always prefer iteration over them.

The fact is that recursion is rarely the most efficient approach to solving a problem, and iteration is almost always more efficient. This is because there is usually more overhead associated with making recursive calls due to the fact that the call stack is so heavily used during recursion.
This means that many computer programming languages will spend more time maintaining the call stack then they will actually performing the necessary calculations.

Does recursion use more memory than iteration? Generally speaking, yes it does. This is because of the extensive use of the call stack.

Should I use recursion or iteration?

Recursion is generally used because of the fact that it is simpler to implement, and it is usually more ‘elegant’ than iterative solutions. Remember that anything that’s done in recursion can also be done iteratively, but with recursion there is generally a performance drawback. But, depending on the problem that you are trying to solve, that performance drawback can be very insignificant – in which case it makes sense to use recursion. With recursion, you also get the added benefit that other programmers can more easily understand your code – which is always a good thing to have.

Answer 3

Correcting other answers: any iteration can be transformed into recursion (with the caveat that a stack overflow may occur). However, not all recursions can be transformed directly into iteration. Often you will need some form of scratch space to hold the data that would otherwise be stored on the stack.

As for which to choose: that depends on your language on and the convenience of writing a recursive solution.

---

Edit, to clarify what I meant by "directly":

There are three types of recursion, based on how directly they can be converted to iteration:

• Tail-call optimizable, in which the very last operation in the method is the recursive call. These can be translated directly into a loop.
• Recursion that is not tail-call optimizable, because it requires information to be preserved between calls, but does not need a stack. A factorial expressed as fact(N) is the classic example: in a recursive formulation, the last operation is not a recursive call, but a multiplication. These types of recursive calls can easily be transformed into a tail-call optimizable form, and thence into an iterative form (to transform factorial into a tail-call optimizable form, you must use a two-argument version fact(n, acc), where acc is the accumulated result).
• Recursion that requires state to be preserved at each call. The classic example is a preorder tree traversal: at each call, you must remember the parent node. There is no way to transform this directly into iteration. Instead, you must construct your own stack to hold the state from each call.

Answer 4

what do you mean better? every recurssion can also be implemented with iterations and vice versa. sometimes recurssion is more easy to understand. however since recurssion inflates the stack , many nested calls may cause out of memory exception.in which case recurssion is clearly not your best choice.

Answer 5

Strictly speaking, recursion and iteration are both equally powerful. Any recursive solution can be implemented as an iterative solution with a stack. The inverse transformation can be trickier, but most trivial is just passing the state down through the call chain.

In Java, there is one situation where a recursive solution is better than a (naive) iterative one, and one situation where they are basically equivalent. In most other cases, the iterative solution will be superior, since function call overhead is avoided.

If the function uses a stack implicitly, then the recursive solution will typically be superior. Consider a depth-first search:

void walkTree(TreeNode t) {
    doSomething(t);

    if (t.hasLeft()) { walkTree(t.getLeft()); }
    if (t.hasRight()) { walkTree(t.getRight()); }
}

compared to the equivalent iterative solution

void walkTree(TreeNode t) {
    Stack<TreeNode> s = new Stack<TreeNode>();
    s.push(t);
    while (!s.empty()) {
        TreeNode t = s.pop();
        doSomething(t);
        if (t.hasLeft()) { s.push(t.getLeft()); }
        if (t.hasRight()) { s.push(t.getRight()); }
    }
}

In the iterative case, you will have to pay for any garbage created by the Stack<> object. In the recursive case, you will use the process stack, which will not create any garbage or allocate any memory. The recursive solution is vulnerable to a stack overflow, but will run faster otherwise.

If the function uses tail recursion, then the two solutions will be equivalent because the JIT will transform the recursive one into the iterative one. Tail recursion is when the last thing that a function does is invoke itself recursively, allowing the compiler to ignore any accumulated state. For example, traversing a list

void walkList(ListNode n) {
    doSomething(n);
    if (n.hasNext()) { walkList(n.getNext()); }
}

Since "walkList" is the last thing done in the function, the JIT will transform it essentially into a "n = n.getNext(); goto beginning", which wil make it equivalent to the iterative solution.

In most other situations, an iterative solution will be superior. For example, if you wanted to do a breadth-first search, then you could use a Queue instead of a Stack in the iterative solution, and have it work instantly, while transforming it to a recursive solution requires that you pay for both the implicit stack in the call stack, and still pay for the queue.

Answer 6

The statement, "Recursion is always better than iteration" is false. There are cases when either one is preferable over the other.

It's difficult to give you a decisive answer over which type of algorithm to use because it depends on the particular case. For example, the common textbook recursion case of the Fibonacci sequence is incredibly inefficient using recursion, so it's better to use iteration in that case. Conversely, traversing a tree can be implemented more efficiently using recursion.

To answer your second question, yes, any iterative algorithm can be implemented using recursion and vice-versa.

Answer 7

Usually recursive methods demands a few lines of code but a deeply thought about your algorithm. If you make a logical mistake, you'll probably obtain a StackOverflowError.

Here follows 2 programming examples for factorial:

Iteractive:

public int calculateIteractiveFactorial(int n) {
    // Base case
    if (n == 1) {
        return 1;
    }
    int factorial = 1;
    for (int i = 1; i <= n; i++) {
        factorial = factorial * i;
    }
    return factorial;
}

Recursive:

public int calculateRecursiveFactorial(int n) {
    // Base case
    if (n == 1) {
        return 1;
    }
    return n * calculateRecursiveFactorial(n - 1);
}

It's always good to reflect about different ideas for each proposal, always considering lines of code, complexity, clarity, cohesion, etc.

Answer 8

If we remember the pass by value mechanism of java we can understand that the recursion consumes more memory as for each call you pass a copy of the object reference address or value of some primitive type. So as mach parameters you pass for each recursive call as mach memory you will consume for each call, on the other hand loops are light to use. But of course we know that there are "divide and conquer" algorithms for example Mergesort or iterations on tree's which consume less steps with help of recursion for giving a result. So in these cases i think it is better to use recursion.