What is a practical difference between a loop and recursion

Question

I am currently working in PHP, so this example will be in PHP, but the question applies to multiple languages.

I am working on this project with a fiend of mine, and as always we were held up by a big problem. Now we both went home, couldn't solve the problem. That night we both found the solution, only I used a loop to tackle the problem, and he used recursion.

Now I wanted to tell him the difference between the loop and recursion, but I couldn't come up with a solution where you need recursion over a normal loop.

I am going to make a simplified version of both, I hope someone can explain how one is different from the other.

Please forgive me for any coding errors

The loop:

printnumbers(1,10);

public function printnumbers($start,$stop)
{
    for($i=$start;$i<=$stop;$i++)
    {
        echo $i;
    }
}

Now the code above just simply prints out the numbers.

Now let's do this with recursion:

printnumbers(1,10);

public function printnumbers($start,$stop)
{
    $i = $start;
    if($i <= $stop)
    {
        echo $i;
        printnumbers($start+1,$stop);
    }
}

This method above will do the exact same thing as the loop, but then only with recursion.

Can anyone explain to me what there is different about using one of these methods.

Answer 1

Compared to loops, a function call has its own overhead like allocating stack etc. And in most cases, loops are more understandable than their recursive counterparts.

Also, you will end up using more memory and can even run out of stack space if the difference between start and stop is high and there are too many instances of this code running simultaneously (which can happen as you get more traffic).

Answer 2

Well, I don't know about PHP but most languages generate a function call (at the machine level) for every recursion. So they have the potential to use a lot of stack space, unless the compiler produces tail-call optimizations (if your code allows it). Loops are more 'efficient' in that sense because they don't grow the stack. Recursion has the advantage of being able to express some tasks more naturally though.

In this specific case, from a conceptual (rather than implementative) point of view, the two solutions are totally equivalent.

Answer 3

Loops and recursions are in many ways equivalent. There are no programs the need one or the other, in principle you can always translate from loops to recursion or vice versa.

Recursions is more powerful in the sense that to translating recursion to a loop might need a stack that you have to manipulate yourself. (Try traversing a binary tree using a loop and you will feel the pain.)

On the other hand, many languages (and implementations), e.g., Java, don't implement tail recursion properly. Tail recursion is when the last thing you do in a function is to call yourself (like in your example). This kind of recursion does not have to consume any stack, but in many languages they do, which means you can't always use recursion.

Answer 4

In general, a recursive function will consume more stack space (since it's really a large set of function calls), while an iterative solution won't. This also means that an iterative solution, in general, will be faster because.

I am not sure if this applies to an interpreted language like PHP though, it is possible that the interpreter can handle this better.

Answer 5

A loop will be faster because there's always overhead in executing an extra function call.

A problem with learning about recursion is a lot of the examples given (say, factorials) are bad examples of using recursion.

Where possible, stick with a loop unless you need to do something different. A good example of using recursion is looping over each node in a Tree with multiple levels of child nodes.

Answer 6

Recursion is a bit slower (because function calls are slower than setting a variable), and uses more space on most languages' call stacks. If you tried to printnumbers(1, 1000000000), the recursive version would likely throw a PHP fatal error or even a 500 error.

There are some cases where recursion makes sense, like doing something to every part of a tree (getting all files in a directory and its subdirectories, or maybe messing with an XML document), but it has its price -- in speed, stack footprint, and the time spent to make sure it doesn't get stuck calling itself over and over til it crashes. If a loop makes more sense, it's definitely the way to go.

Answer 7

Often, a problem is easier expressed using recursion. This is especially true when you talk about tree-like data structures (e.g. directories, decision trees...).

These data structures are finite in nature, so most of the time processing them is clearer with recursion.

When stack-depth is often limited, and every function call requires a piece of stack, and when talking about a possibly infinite data structure you will have to abandon recursion and translate it into iteration.

Especially functional languages are good at handling 'infinite' recursion. Imperative languages are focused on iteration-like loops.

Answer 8

You don't really need recursion for a flat structure like that. The first code I ever used recursion in involved managing physical containers. Each container might contain stuff (a list of them, each with weights) and/or more containers, which have a weight. I needed the total weight of a container and all it held. (I was using it to predict the weight of large backpacks full of camping equipment without packing and weighing them.) This was easy to do with recursion and would have been a lot harder with loops. But many kinds of problems that naturally suit themselves to one approach can also be tackled with the other.

Answer 9

Stack overflow.

And no, I don't mean a website or something. I MEAN a "stack overflow".