Recursion!


#1

Could anyone specifically give me a situation (Preferably in Python, but I'll take another language) where recursion is used in a function.

The same effects you create with recursion could also be done with loops (As far as I've seen).

So why is recursion necessary? It is just to save time writing code, or for runtime efficiency?

Thanks for answering,
Cade


#2

Not an expert on this so happy for someone else to say I'm wrong :slightly_smiling:

But I think any situation you need recursion can be done with loops, as that is almost the definition of recursion: looping code.

Recursion is generally used to make it easier to read the code, and its useful for tree traversal, directories etc. So it is easier for us but since it is just a lot of function calls it will take up more stack space so will normally take longer to run than a similar loop implementation.

Theres a lot of talk on stackoverflow etc. about this is you search Recursion vs Loops.


#3

@alexcraig
Thanks for replying,

I've searched a couple places, and I've seen that I'd much rather use loops over recursion for everything, except trees which you mentioned.

The amount of time it takes compared to a loop is huge! So I'd rather go with the faster but sometimes less efficient choice, the good old loop, :slightly_smiling:


#4

Recursion can look very elegant though. E.g. a one line Fibonacci:

function f(n) {return (n < 2) ? n : f(n-1) + f(n-2); }

So it is useful as you can write less code using it, but at the downside it takes longer to execute.


#5

Allow me to "explain" how quicksort works.

A sequnce of length 1 or less is already sorted.
choose the first value as pivot
result = sorted(less or equal) + the pivot itself + sorted(greater)

I'm essentially just stating the obvious, yet this is an efficient sorting algorithm.

def quicksort(seq):
    if len(seq) <= 1:
        return seq
    pivot = seq[0]
    less = quicksort([value for value in seq[1:] if value < pivot])
    more = quicksort([value for value in seq[1:] if value >= pivot])
    return less + [pivot] + more

If you describe this as a loop, things get messy.

Another example is navigating a labyrinth:

If got out, done
mark this position as visited
recurse on each choice
un-mark this position

Again, a loop ends up a mess.

Tower of Hanoi?
Moving one ring is easy.
If we know how to move one ring, then it's easy to move two rings.
If we know how to move two rings, then it's easy to move three rings.
if we know how to move three rings, then it's easy to move four rings.
if ...

With a loop? Uhh. No.