Algorithms Explained: Recursion

If you’re just starting out with programming you may have heard the word recursion being thrown around. You may have even come across problem questions stating ‘Find a recursive solution to solve X’ etc.

Before I go any further I want to say this, writing a recursive solution is DIFFICULT when starting out. Don’t expect it to work first time. Writing a recursive solution involves a whole new way of thinking and can in fact be quite off putting to new comers but stick with it and you’ll wonder how you ever found it so difficult.

So what exactly is recursion? A recursive solution is one where the solution to a problem is expressed as an operation on a simplified version of the same problem.

Now that probably didn’t make a whole lot of sense and it’s very tricky to explain exactly how it works so lets look at a simple example:

def reduce(x):return reduce(x-1)

So whats happening here? We have a function called reduce which takes a parameter ‘x’ (an integer) and we want it to reduce it to ‘0’. Sounds simple so lets run it when we pass 5 as the parameter and see what happens:

>>> reduce(5)RuntimeError: maximum recursion depth exceeded

An error? Well lets take a closer look at whats going on here:

reduce(5) calls reduce(4) which calls reduce(3)…….Thus our initial call reduce(5) is the first call in an infinite number of calls to reduce(). Each time reduce() is called, Python instantiates a data structure to represent that particular call to the function. This data structure is called a stack frame. A stack frame occupies memory. Our program attempts to create an infinite number of stack frames which would require an infinite amount of memory which we don’t have so our program crashes.

To fix this problem we need to add in something referred to as the base case. This is simply a check we add so that our function knows when to stop calling itself. The base case is normally the simplest version of the original problem and one we always know the answer to.

Lets fix our error by adding a base case. For this function we want it to stop when we reach 0.

def reduce(x):if x == 0:return 0return reduce(x-1)

So now when we run our program we get:

>>> reduce(5)0

Great it works! Lets take another look at what is happening this time. We call reduce(5) which calls reduce(4)….which calls reduce(0). Ok stop here, we have hit our base case. Now what the function will do is return 0 to the previous call of reduce(1) which returns 0 to reduce(2)….which returns 0 to reduce(5) which returns our answer. There you go, your first recursive solution!

Let’s look at a more practical example. Lets write a recursive solution to find N! (or N factorial):

N factorial is defined as: N! = N * (N-1) * (N-2)…… * 2 * 1.

For example, 4! = 4 * 3 * 2 * 1

Our base case for this example is N = 0 as 0! is defined as 1. So lets write our function:

def factorial(n):if n == 0:return 1return n * factorial(n-1)

OK lets see that in action. We’ll call our function and pass 4 in for n:

factorial(4) calls factorial (3) ….. which calls factorial(0) which is our base case so we return 1 back to the previous call of factorial(1) which takes our 1 and multiplies it by 1 which evaluate to 1 which passes that back to factorial(2) which takes our 1 and multiplies it by 2 which evaluates to 2 which passes that back to factorial(3) which multiplies 3 *2 to get 6 which passes that back to factorial(4) which multiples 4 * 6 which evaluates to 24 which is returned as our answer.

These are very simple cases and not super useful but being able to spot when a recursive solution may be implemented and then implementing that solution is a skill that will make you a better programmer. For certain problems recursion may offer an intuitive, simple, and elegant solution.

For example, you may implement a recursive solution to find the number of nodes in a tree structure, count how many leaf nodes are in a tree or even return whether a binary search tree is AVL balanced or not. These solutions tend to be quite short and elegant and take away from the long iterative approach you may have been taking.

As I’ve said, recursion isn’t easy but stick with it, it will click and seem so simple you’ll wonder how you ever found it so difficult.

If you’re interested in more tutorials like these, head over to www.pyler.io where you can find many great Python courses that will take you from beginner to advanced in no time!

We currently have 20% off our Introduction to Python course (Now only €39.99) were you will have a mentor to guide you through the course and lend a helping hand if you feel stuck!

Plus, receive a FREE copy of ‘Slither into Python’ when you enroll in any course!

‘Slither into Python: An introduction to the Python programming language’