Discover How to Build Programs With Algorithms

In programming, we’ve seen that we can use loops to repeat an operation. We call these iterative loops. We’re now going to take a more detailed look at a concept we touched on earlier in the course—recursion.

It’s a very specific concept. Have you ever dreamed you were dreaming? That’s more or less it! It’s all about concepts which refer to themselves. Let’s find out more!

Find out About Recursion

Recursion is a concept which works by referring back to itself.

Russian dolls are an excellent metaphor for recursion. Each doll is the same, except for its size, and each doll opens up to reveal a smaller doll inside it, until you get to the smallest one in the center, which doesn’t open. When you reach the smallest doll, you go through the whole process again, closing each doll in the opposite order.

In actual fact, we use recursion every day when we speak! We use words to define other words, which themselves are defined by other words.

Understand Recursion in Programming

In programming, we can talk about recursion when a function refers back to itself. When two functions call each other, this is known as mutual recursion.

Let’s try to transcribe the example of the Russian dolls using a recursive function. We’re going to use it to count the number of dolls.

First, we need to create a function which takes a doll as a parameter, whether or not it contains another doll:

Number_of_dolls(doll) algorithm
Start

End

Now we can create the body of the function. If the doll used as a parameter contains another doll, we return 1 to count this doll, and we call the same function recursively to check if the other doll also contains a doll.

Number_of_dolls(doll) algorithm
Start
   If doll contains another doll:
      Return 1 + number_of_dolls(doll inside)
   End If
End

To finish, we need to find a way of stopping this recursive function, otherwise we’ll end up with an infinite loop. If the doll doesn’t contain another doll, we want the function to simply return 1 to count it, and then stop.

This is the complete function:

Number_of_dolls(doll) algorithm
Start
   If doll contains another doll:
      Return 1 + number_of_dolls(doll inside)
   Else
      Return 1
   End If
End

Like with loops, we always need to add a condition to stop recursive calls. 

Discover The Fibonacci Sequence

Anyone who’s ever had a job interview for a role as a developer will certainly have heard of the Fibonacci sequence! One of the most common problems candidates are asked to solve in interviews is “given an input n, find the nth number in the Fibonacci sequence.”

The Fibonacci sequence is a list of whole numbers. It generally starts with the numbers zero and one (or sometimes one and one). Numbers in this list are called terms. Each term is the sum of the two previous terms.

For example, if we take the start of the Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, etc., you can see that 0 + 1 equals 1, 1 + 2 equals 3, 2 + 3 equals 5, and so on.

We’re going to use algorithms to solve the problem mentioned above: given an input n, find the nth number in the Fibonacci sequence. There are many ways of doing this. Take a few minutes to think about the different algorithms you could invent.

We’ll use a recursive method and an iterative method, so you can compare the two possibilities.

The Naive Recursive Algorithm Method

A naive algorithm is a “simple” algorithm, based on the most obvious solution that springs to mind to resolve a problem.

In our case, we can write:

Fibonacci(n) algorithm
Start
   If n <= 1:
      Return 1
   Else
      Return fibonacci(n - 1) + fibonacci(n - 2)
   End If
End

If we call the  fibonacci  function with the parameter as “3”  fibonacci(3)  , the function returns 3. But why?

• fibonacci(3)  : calls the functions  fibonacci(2)  and  fibonacci(1)  :

  • fibonacci(1)  : this function stops and returns 1.

  • fibonacci(0)  : this function stops and returns 1.

  • So,   fibonacci(2)  returns 1 + 1.

  • fibonacci(2)  : calls the functions  fibonacci(1)  and  fibonacci(0)  .

  • fibonacci(1)  : this function stops and returns 1.

• Finally, we add up what  fibonacci(2)  and  fibonacci(1)  return, i.e., 2 + 1. 

So  fibonacci(3)  = 3.

The problem with this method is that it takes up a lot of memory. This is because it’s an exponential calculation—it requires two different calculations to calculate itself.

When we calculate the value of a number, we carry out the three following operations:

• Calculate fibonacci(n-1) [which itself calculates fibonacci (n-1) and so on until it gets to the figure 1] and store the value in the memory. 

• Calculate fibonacci(n-2) [do the same each time until it gets to 1] and store the value in the memory. 

• Finally, add the two values. 

We can see that this is an exponential calculation—each new number requires twice as much memory as the previous one. Its complexity is $\$\backslash (O(2^n)\backslash )\$$.

That’s where linear algorithms come in useful!

The Linear Algorithm Method

What if you calculated two consecutive values, one after the other? That would be a better solution, wouldn’t it?

We can write the following function:

Fibonacci(n) algorithm
Variable
   a ← 0 : INTEGER
   b ← 1 : INTEGER
   c ← 0 : INTEGER
Start
   For i from 1 to n:
      c ← a + b
      a ← b
      b ← c
   Return b
End

Each new number now only needs one line of operations, rather than two. This algorithm is therefore linear, and its complexity is $\$\backslash (O(n)\backslash )\$$ .

We can see here that, in many cases, it’s better to use the iterative version, as it uses less memory. Recursion isn’t the solution to every problem!

Here are the important steps involved in programming a recursive function:

1. Break a problem down into one or more subproblems of the same type. The subproblems can be solved using recursive calls. 

2. Subproblems must be smaller than the initial problem.

3. Breaking down a problem should lead to a basic element which can’t be broken down into further subproblems. This is its base case.

Remember when we broke down each function call recursively for the Fibonacci sequence problem? We looked at the order in which each function was called to identify the final result of these recursive calls. The computer automatically stacks each function call to determine the right order, and know which functions are active. This is what’s known as a call stack.

Discover Call Stacks

The computer has to remember the result of all the recursive calculations before ending the loop. To do this, it uses a call stack, which is automatically generated by the system.

As an example, let’s take a look at this function,  main  , in the maze:

Main() algorithm
Variable
   player_position_x ← 0 : INTEGER
   player_position_y ← 0 : INTEGER
   end_position_x ← 5 : INTEGER
   end_position_y ← 5 : INTEGER
   keys[3] : ARRAY STRING
Start
   While player_position_x != end_position_x AND player_position_y != end_position_y AND keys.size() != 3:
      moves(player_position_x, player_position_y)
      pick_up(keys, player_position_x, player_position_y)
   End While
End

 When the  main  function is called, it’s placed in the call stack:

It remains there for as long as it’s active, i.e., until it ends. 

Then, in the  main  function, we call the  moves  function a first time in the  while  loop, and it’s also added to the call stack, above the  main  function.

Straight after, the  moves  function ends, so it’s “popped,” i.e., removed, from the stack:

On the following line, the  pick up  function is called, so it’s “pushed,” i.e., added to the stack. We now get this:

The  pick up  function is also popped when it’s finished, and so on for as long as the loop is active. When the loop ends, the main function ends too. The  main  function is then also popped from the call stack. When the stack is empty, the program is finished!

That is exactly what happens in the case of a recursive call!

Let’s take a look at this recursive function:

Counter(n) algorithm
   If n > 0 :
      counter(n - 1)
   End If
   Display n
End

Push

When we call the  counter  function with  n=2 , we get the following call stack:

All recursive calls within the  counter  function are pushed onto the call stack.

Pop

When the last recursive function is called, the computer “pops” all of the functions from the call stack. In other words, it looks through the stack to find the last element saved, and so on until it gets to the bottom of the stack. This comes in very useful!

Over to You!

Context

To finish our maze, we’re going to add a last feature. We’re going to set some traps on certain squares, which will immobilize the player for 10 seconds when they land on them.

Instructions

To do this, you’ll need to create a recursive function which immobilizes the player for n seconds, and displays a countdown of the time left before they’re set free again. We’ll call this function  freeze  .

Using the function  wait , you can pause the game for a certain number of seconds. The number of seconds is passed as a parameter of the function.

Your Mission 

• Define a  freeze  function which takes the number of seconds of immobilization, n, as a parameter. 

• Display the number of seconds remaining.

• Pause the game for one second.

• Recursively call the  freeze  function.

• Specify the base case of the recursive function.

Check Your Work

Here’s what the result of the exercise should look like:

Freeze(n) algorithm
   If n == 0 :
      stop the recursive call
   End If

   Display n
   wait(1)
   freeze(n - 1)
End

Let’s Recap!

• A recursive function is a function which calls itself during its execution.

• The steps for creating a recursive function are:

  • Break the problem down into one or more subproblems of the same type. These will be solved using recursive calls. 

  • Subproblems must be smaller than the initial problem.

  • Finally, breaking down a problem must result in a basic element which can’t be broken down into further subproblems. This is the base condition. 

• A call stack saves information on the active functions in a computer program.

You made it—this is the end of the course! Well done for all your hard work! There’s just one quiz left to put your new knowledge to the test. I know how much you love quizzes!