Recursion!

Community Off Topic
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.

6

could you please explain this again in simpler terms ?
i think i understand what you are getting at, but i am not sure that i do .
please correct me if i am wrong … it is more useful in ending a loop; but couldn’t we then use a a conditional and break out of it or am i mistaken ? or would I be complicating things ?

7

Hello, @koseitakeddin.

Sadly, @ionatan hasn’t been seen on the forums in a couple of years now. This topic is also many years old. There are others present on the forums that can probably assist you, though maybe not at the same level @ionatan could have were he still around. I suggest starting a new topic potentially under the language you are working in, and ask a specific question with your code examples.

1 Like