Recursion is the code equivalent of a fancy parlor trick. First you have this top hat, then you wave your (code) hands around mysteriously, and all of the sudden a chinchilla appears. Sure, you could have just walked into another room, picked up Baby Chinchy, and brought it back out to the party, but that's boring. What makes the magic trick shine is the style of how your favorite rodent is presented.

It looks really clean to write things recursively, which is why people (read: mathematicians) love using it. Everything is laid out in the program elegantly and precisely. The clunkier version (read: iterative loops) is the code equivalent of bringing your audience back into the chinchilla cage and doing away with the top hat all together. It just isn't as elegant.

Mathematicians write proofs in recursive formats (using certain rules about numbers to make assumptions that different truths for specific numbers will always work for any numbers). It just feels more natural to write recursively sometimes. We know, we know, that sounds counter-intuitive, but think about it for a moment with us.

A Recursive Example

Fibonacci is defined as a pattern where every number is the sum of the two numbers before it. To find the n^th number, you have to find n – 1 and n – 2. That definition just begs for a recursive solution because the problem relies on sub-problems being solved before it can be solved.

That being said, what recursion adds in the beauty department, it loses in the time inefficiencies and (sometimes) oversight of logic flaws. Iterative loops don't have to rely on the call stack to store all their data, which means that when data gets large, they don't immediately run the risk of a stack overflow. Recursive functions do. Plus, if a loop is going to continue infinitely, it's much more obvious than if a recursive function is.

That Fibonacci sequence? Its recursive version is going to take a runtime of O(2ⁿ). The minute that function gets a really large number, it's going to cause a stack overflow. Contrast that with the iterative implementation, which would take one loop (from 0 to n), making the runtime O(n). That's a huge difference.

Conclusion: recursion might look and feel really pretty, but it isn't always the best way to approach a problem. Save it for problems that can be broken into treelike structures. When there's a balanced treelike structure, the recursion will make things cleaner and faster. We're talking about things like

• binary search trees.
• merge sort.
• Quicksort.
• searching file structures.

Think wisely before you decide to implement a recursive function, Shmooper. It can avoid many sticky situations.