Is it bad practice to use Recursion where it isn't necessary?

Question

In one of my last assignments, I got points docked for using recursion where it was not necessary. Is it bad practice to use Recursion where you don't have to?

For instance, this Python code block could be written two ways:

def test():
    if(foo() == 'success!'):
        print(True)
    else:
        test()

or

def test():
    while(True):
        if(foo() == 'success!'):
            print(True)
            break

Is one inherently better than another? (Performance-wise or Practice-wise)?

Might be worth taking a look at this question too https://stackoverflow.com/questions/72209/recursion-or-iteration — Totem, Oct 15 '15 at 18:33
This is almost like the goto vs loop argument in other languages. I would usually refactor my code to take advantage of loops where possible, since control flow is usually better managed inside of a loop. — MeetTitan, Oct 15 '15 at 18:45

score 7 · Accepted Answer · answered Oct 15 '15 at 18:31

While recursion may allow for an easier-to-read solution, there is a cost. Each function call requires a small amount of memory overhead and set-up time that a loop iteration does not.

The Python call stack is also limited to 1000 nested calls by default; each recursive call counts against that limit, so you risk raising a run-time error with any recursive algorithm. There is no such hard limit to the number of iterations a loop may make.

BrianO · Answer 2 · 2015-10-16T21:08:03.147

They're not the same. The iterative version can in theory run forever, once it is entered it doesn't it doesn't change the state of the Python virtual machine. The recursive version, however, keeps expanding the call stack when keeps going. As @chepner mentions in his answer, there's a limit to how long you can keep that up.

For the example you give, you'll notice the difference quickly! As foo never changes, when foo !='success!' the recursive version will raise an exception once you blow out the stack (which won't take long), but the iterative version will "hang". For other functions that actually terminate, between two implementations of the same algorithm, one recursive and the other iterative, the iterative version usually will outperform the recursive one as function calls impose some overhead.

Generally, recursions should bottom out -- typically there's a simplest case they handle outright without further recursive calls (n = 0, list or tuple or dict is empty, etc.) For more complex inputs, recursive calls work on constituent parts of the input (elements of a list, items of a dict, ...), returning solutions to their subproblems which the calling instance combines in some way and returns.

Recursion is analogous, and in many ways related, to mathematical induction -- more generally, well-founded induction. You reason about the correctness of a recursive procedure using induction, as the arguments passed recursively are generally "smaller" than those passed to the caller.

In your example, recursion is pointless: you're not passing data to a nested call, it's not a case of divide-and-conquer, there's no base case at all. It's the wrong mechanism for "infinite"/unbounded loops.

Is it bad practice to use Recursion where it isn't necessary?

2 Answers2