Python recursion explained like for a 4 year old.

What is a recursion?

According to wikipedia a recursion is defined as:

“…a method of solving a problem where the solution depends on solutions to smaller instances of the same problem”

Let’s try to understand this statement using an example and then draw some conclusions.

The philosophy behind recursion:

Let’s look at a problem like calculating 5! (factorial). In order to find out the result of 5! we need to calculate:

Equally we can say that:

It seems that our factorial problem boils down to a “problem where the solution depends on solutions to smaller instances of the same problem”.

If we were to write down the algorithm for this operation it would look like:

Creating recursion logic with for loop:

Recursion and for loop are interchangeble. It seems an intuitive approach to first look at a for loop in action to understand what is going on.

First we will create the for loop function and then we will brake it down.

Let’s understand what the for loop does.

  • The function takes a number n, in our case number 5
  • We define range func to start from 1 to n+1 in order to include (5) and discard the 0 because 0 * any number = 0
  • We define “fact = 1” for initial value because any number multiplied by 1 remains unchanged (1*1 = 1)
  • Inside “for loop” we take previous result and multiply it by the next number (i)

Let’s visualise what happens with each iteration.

Create the recursion:

Recursion will do the same job as for loop however the syntax for recursion is slightly different and may not be very intuitive at first glance but we will break it down step by step.

There are a few things to note here.

  1. IF / ELSE statement… Recursion creates a loop, this loop has to have a condition to stop. For this reason every recursion has an IF / ELSE statement. In our case when n reaches value 1, we return value one and stop the recursion (loop).
  2. In order to create a recursion a function has to call itself. You can see in the else: part of the function.
  3. When the function is calling itself we need to make sure it will reach our base case (n ≤ 1) in order to stop. In our case we decrement n by one Eg: factorial_recursion(n-1)

Visualising Recursion:

Example 2:

Split a word into groups of 2 letters. If word has uneven letters, add “_” to the last letter. The output should be a list with groups of two letters of type string.

  • Recursion continues until len(s) =1.
  • In the solution we start slicing two letters and instruct python to continue untill base case is hit.

Example 3:

Reverse a string using recursion:

Example 4

Create a fibonacci array using recursion.

Passionate about DataScience

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store