Is recursion generally considered to be an outdated method of traversing compared to using a stack?

Question

I've been reading in a couple of places where people are opting to use a Stack instead of recursion. Is this because recursion is seen as being an outdated way to get-the-job-done or are both methods equally applicable in different contexts?

Answer 1

No. Just the opposite. Recursion is the natural way to express a whole class of problems. A stack is a way to simulate that if you don't have recursion.

See, for example, this question. Or consider the sort of standard recursive function: computing the n-th Fibonacci number.

You'll recall that Fibonacci numbers are the series

0,1,1,2,3,5,8,13, ...

defined so that F_n = F_n-1+F_n-2.

This can be written as a recursive definition as

Base case:
F(0) = 0
F(1) = 1
Recursive step:
F(n) = F(n-1)+F(n-2)

So, you have F(0) = 0, F(1)= 1, F(2)=F(0)+F(1)=1, and so on.

A simple program to compute this (in C just for grins) is:

int fib(int n) {
    /* we'll ignore possible negative arguments, see Wikipedia */
    switch(n) {
       case 0: return 0; break;
       case 1: return 1; break;
       default: return fib(n-1)+fib(n-2); break;
    }
}

Notice how closely that program corresponds to the original definition?

The thing is, C manages all the intermediate results in the calling stack. Some languages aren't defined to do that (the only one I can think of offhand is old FORTRAN, but I'm sure there are others). If you are writing in assembler or old FORTRAN, then, you have to manage your own stack to keep track of those intermediate results.

Answer 2

Updated to include fishlips' correction.

Using a Stack is a standard technique of eliminating recursion

See also: What is tail-recursion?

An example of Tail-Recursion (that can be removed using iteration):

public class TailTest
{   
    public static void Main()
    {    
        TailTest f = new TailTest();
        f.DoTail(0);
    }

    public void DoTail(int n)
    {    
        int v = n + 1;   
        System.Console.WriteLine(v);    

        DoTail(v);   // Tail-Recursive call
    }
}

Answer 3

Iteration is often faster/ has less overhead than recursion. With recursion, we implicitly use the machine's stack as our stack -- we get that "for free" -- but we pay the cost of expensive function calls (and attendant machine stack management).

But recursive functions are often more intuitive to write and to read.

Often, it's possible to write a function using recursion, leave that until it becomes a bottleneck, then replace it with an iterative function that uses an explicit stack.

Answer 4

If you are in a programming language/environment where tail calls grow the stack (no tail call optimization (TCO) applied), then it is best to avoid deep recursion, and iterative solutions that may use a stack data structure are preferred.

On the other hand, if you are in a language/environment that supports iterating with tail calls, or if the recursion depth will always be small, then recursion is often a fine/elegant solution.

(This is a little over-broad, but overall, I would by no means call recursion "out-dated".)

Answer 5

No no, I think modern developers should emphasize readibility and ease of maintenance over some miliseconds.

If the problem IS recursive, I fully recommend your solution to BE recursive.

Besides, you may end up introducing some unespected bugs tryng to force an iterative/stacked solution.