What's the difference between nested loops, and recursive functions?

Question

What's the difference in the output in using a nested loop or a recursive function. Which is the best one for generating combinations while accounting for conditions?

It depends on the specific problem you're trying to solve. You won't simply use one instead of the other all of the time. Note "[Understanding recursion](http://stackoverflow.com/questions/717725/understanding-recursion)" — Jonathan Lonowski, Oct 19 '14 at 17:11

score 1 · Answer 1 · edited May 23 '17 at 10:33

Recursion can be seen as "just" another way of doing loops. The main advantage is code readability, as you can see in this Stackoverflow question, in this case when there are a lot of nested loops.

Be careful however, as there is a small recursion limit on Python (1000). You can verify by typing

>>>import sys
>>>print sys.getrecursionlimit()
1000

For an overview of other cases of recursion vs loops, check out this pdf. However, as stated in this Stackoverflow answer, you should stick to a purely iterative scheme on Python.

score 1 · Accepted Answer · edited Jan 28 '15 at 19:38

A recursive algorithm calls a function from within that same function (recursion). Whether to perform the recursion is based on some condition.

    function foo()
    {
            ?/ do work
            if( condition )
                    foo();
    }

An iterative algorithm typically calls a function some number of times (n).

    function foo()
    {}

    for(int i = 0; i < n; i++)
            foo();

A recursive function is typically used when some piece of data needs to be manipulated repeatedly and the condition of whether to repeat is dependent on the previous manipulation. Computing a truncated infinite series in math is an example of this.

An iterative function is typically used when the condition is not dependent on the previous manipulation. Inverting a matrix has a predefined n.

Either method can be used for most purposes, but you will typically find that one is easier than the other for a particular case.

Be aware of callstack overflow with recursion though. It is best to only use it if you can guarantee that the algorithm will converge and end within some number of recursions.

Stefano Sanfilippo · Answer 3 · 2014-10-23T20:46:35.720

Recursion and iteration (loops) are different strategies which are not comparable in a general sense. For some algorithms, you might have both an iterative and a recursive version (such as factorial or Fibonacci numbers), for some others one of the two could be more intuitive than the other (such as recursive for tree walking).

Regardless of the strategy which the algorithm follows, the output must be the same, otherwise you would have implemented a different algorithm.

Bottom line, it really depends on what algorithm you will be using.

What's the difference between nested loops, and recursive functions?

3 Answers3