Recursion

Recursion is a vital concept in computer science. It is a definition or function that calls itself. It essentially breaks one large problem with many doors into smaller problems until there is no door left unopened.

So why is this concept so vital?

Because we don't possibly have the time to calculate or resources to calculate each equation individually. For this same reason, we also iterate, and depending on the problem you will either want to recurse or iterate.

Recursion can be a more concise way of writing code as opposed to writing several loops and it can also execute much more rapidly. That does not mean that it is more efficient, however. Recursive definitions tend to be more expensive than loops. Generally speaking, a standard loop is cheaper than a recursive definition.

Marijn Haverbeke said it best: "The dilemma of speed versus elegance is an interesting one. You can see it as a kind of continuum between human-friendliness and machine-friendliness. Almost any program can be made faster by making it bigger and more convoluted." A useful rule-of-thumb is that you should use recursion SPARINGLY and it is most useful for problems that require exploration of many branches of information.

Imagine recursion as rapidly picking apples from a tree until there are none left.

It is helpful to think of recursion in terms of traversing the branches of a fruit tree. As we traverse different branches, we try to uncover information (yellow or red apples) and see if it meets our base case (completely barren branches). You can think of the base case as a condition that needs to be met before you can climb to a different branch to collect additional apples. Once you hit the base case, your loop ends.

There are two essential parts of recursion:

• Base Case — where a condition is met and we exit the function
• Recursive Case — where the function calls itself

WARNING: Stack Overflow

If you write an incorrect base case or omit one altogether, it is easy to run into a stack overflow error caused by an infinite loop. This will say “SystemStackError: stack level too deep”.

Our most basic recursive problem is the factorial function. We all remember being in math class and tackling this problem.

Find the Factorial of a Given Number

n!=n×(n−1)×(n−2)×…×2×1n!=n×(n−1)×(n−2)×…×2×1

Applying recursion to the factorial problem.

A Real-Life Example of Recursion

• searching through all of the folders on your laptop

Additional Tools

Python Tutor

• useful tool for breaking down recursion problems and visualizing code execution in general