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

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 2

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.