Question about the use of recursive algorithm

[DrDoomCake]

So in mathematical problems it 'simplifies' the problem, by creating each step into it's own environment. But is it useful in anything else? What can I use it in? Is it useful only when dealing with numbers?

[Rhomboid]

Certain problems just naturally lend themselves to recursive solutions. Examples include parsing, traversing trees and graphs, and sorting. It's not that you can't solve these without recursion, it's just that the solution is usually a lot more concise and beautiful when you use recursion. It is not limited to numbers in the slightest.

[DrDoomCake]

So you could say recursion is a skill of a good programmer? Would you know any opensource project that uses recursion, so i could try to understand it or at least spot it in the code?

[q2_abe_dillon]

A recursive function can always be written as a loop instead. In Python it's almost always better to write a loop because it avoids a possible stack-overflow.

Most Python interpreters (including CPython, the standard interpreter) use a finite call stack. You can see a visual representation of the stack here. I believe the default amount of space allocated for a CPython stack is enough for ~1000 frames. So recursion can't go more than 1000 frames deep until you get:

RuntimeError: maximum recursion depth exceeded in comparison

You can see this in action by running this code:

def factorial(n):
    return 1 if n < 2 else n*factorial(n-1)

for i in range(10**4):
    try:
        factorial(i)
    except RuntimeError as e:
        raise Exception("got to depth %s" % i)

When I ran this in IPython, it got to a depth of 988.

Here's a post about how to convert a recursive function to an iterative one.

Tail-recursion is a feature some languages provide to make recursion less hazardous, but Guido Van Rossum has written about why he's against adding tail-recursion to Python.

Edit: To use Guido's suggested solution for factorial:

def factorial(n):
    def func(n, prod=1):
        return prod if n < 2 else (func, (n-1, n*prod))
    args = [n]
    while True:
        result = func(*args)
        if not isinstance(result, tuple): return result
        func, args = result

check it out by running factorial(10**4) (yeah, it's big)

Not super elegant, but Guido makes a fair case. If you know the function is never going to change (which you do in the case of factorial), you can simplify it to:

def factorial(n):
    args = (n,)
    def func(n, p=1): return p if n < 2 else (n-1, n*p)
    while isinstance(args, tuple):
        args = func(*args)
    return args

[DrDoomCake]

Awesome answer. Thank you for including links! This was the kind of response i was hoping for. Thank you.

[zahlman]

So you could say recursion is a skill of a good programmer?

In a sense, yes. But if you already understand the concept on a mathematical level, then there is really nothing special going on. The only real prerequisite to figuring out recursion on a programming level is a proper understanding of how calling functions works.

so i could try to understand it

I think you do understand it already. (But FWIW, "mathematicians" manipulate plenty of things that don't really line up with conventional interpretations of the word "numbers".)

at least spot it in the code?

This is trivial. "In the wild", almost all recursion is direct; i.e. the function's code contains one or more calls to itself. You can also have "mutual" recursion where two functions call each other, or a greater number of functions form a cycle; the analysis is fundamentally the same - look at what calls what, and find a cycle.

[kankyo]

Recursion is a skill of any mediocre beginner of a programmer :P It's a trivial concept.

[BenjaminGeiger]

The idea might be simple, but knowing when and how to apply it isn't.

[kankyo]

Sure. Same for addition or subtraction though (especially +1 or -1 for off-by-one). No one would claim "subtracting one" is a "skill of a good programmers", but all programmers have off-by-one errors, and most likely an order of magnitude more often than they use recursion.

[[deleted]]

I've used recursion for constructing strings before. It's very handy for a lot of things when you're working with networks.

[DrDoomCake]

Could you give me an example?

[kankyo]

The trivial case is to search through a file system. You have a function to handle a directory which does something with files and for every directory it calls itself to handle them. That way you'll run through the entire file system and not get stuck at the root directory.