A journey in algorithmic. Week 2 - Recursive programming

Last week, I gave a definition of algorithms and we explored two simple examples to illustrate the concept. Starting today, and for the next few weeks, I will present different class of algorithms that I think will give you a good overview of the field. To start with, I will talk this week about recursive programming.

In my last article, I stated that an algorithm can be considered as a function that uses a set of instructions and input-data to produce output-data. But we did not go into further detail regarding the set of instructions available for the programmer. Let’s dive in!

Programming languages include a set of built-in primitives such as read file loveletter.txt, add 10 and 5, if name is “Matthieu” then print “Bravo” else print “Too Bad”, repeat until victory equals True, Set V to 10, etc. But programming languages also allow you to enrich the set of instructions by writing functions. A function can be considered as an implementation of an algorithm in a specific programming language, Python for instance. A function can then be used as any of the built-in primitives. To sum up, the set of instructions available for the programmer are the built-in primitives of the computer language and the user-defined functions. What about a simple example to illustrate this?

Following up with the example of last week, let us consider the function that calculates the length LD of the diagonal of a rectangle R given its length L and its height H. This function is defined as:

diagonal (L, H) = square root (L * L + H * H).

Note that this function doesn’t use any function but only the built-in procedures +, * and square root.

Let’s now consider the disk D that best includes the rectangle R and whose area we want to calculate.

Figure 1: Rectangle R, its diagonal of length LD and the disk D

We know from our good old days at school that:

area = pi * radius2 where radius is half of the length LD of the diagonal of rectangle R.

Let’s now write our program:

Def diagonal (L, H):

	return square root (L * L + H * H) 

def area (L, H):

	return pi * (diagonal (L, H) / 2) 2:        

The function area uses the build-in primitives *and square, and the function diagonal. We say that the function area “calls” the function diagonal.

That was quite a long introduction, but we know have all the elements to define what is a recursive algorithm: an algorithm is said to be recursive if and only if the function to implement it calls itself! Wow, what does it mean? Do not worry, you will understand with the following examples. In other words, it means that you solve a problem P of size N by solving one (or several) problem(s) P (K) with K < N and so on until we reach a size S that is so small that the result of P (S) becomes trivial.

Still hard to figure out? Let’s take a simple example. Say you want to bet on a horse race with N horses and you want to figure out the number of possible results, to see if betting is worth it! So how many horse combinations? Think recursive, think how to reduce the problem with N horses to one or more problems with less than N horses. Got it? You take all possible results for a race with N-1 horses and, for each of them, insert a new horse at each possible position.

Figure 2: 3 possible results for a 3-horses race by expanding a 2-horses race result

According to the above figure, there are 3 possible 3-horses race results from a given 2-horses race result. This result can be generalized according to the following formula: there are N possible N-horses race results from a given N-1-horses race result. In other words, HorseRaceResults (N) = N * HorseRaceResult (N-1) for N > 1 and HorseRaceResult (1) = 1 (if there is only one horse, there is only one possible result. Some would say it is not even a race but that is not our concern here ??). Those who studied mathematics will recognize the factorial function. So, let’s see how to implement it in pseudo-Python pseudo-code:

Def factorial (N):????????# Def means “definition of a function" with input N 

??????????????if N = 1: return 1

??????????????else: return N * factorial (N-1)  #Return means “the result of the function is…”        

And that’s it! The factorial function on size N calls the factorial function on size N-1 that calls the factorial function on size N-2 and so on until we reach factorial (1) that is trivial to solve: you got your first recursive algorithm!

Recursive algorithms are very powerful: they are used to solve some problems that could be complex otherwise. To illustrate this, I will present here two representative examples of recursive algorithms: “Hano? Towers” and “Compte est bon”.

“Hano? Towers” is a game where you have a pile of N disks of different sizes and 3 towers. You can move disks from one tower to another, but only one disk by one disk (the one on top of the tower), and you are not allowed to put a disk on top of a smaller disk (see figure below).

Figure 3: Example of Hanoi Towers moves with 3 disks

The goal of the game is to move the whole pile of N disks from Tower 1 to Tower 3.

Figure 4: Goal of the Hanoi towers (N = 6 disks)

So, we want to write a function called HanoiTowers that takes as inputs the start tower, the finish tower (and the third tower), and that returns the sequence of moves to be performed.

At first glance, it seems to be quite a difficult task! But this is where the magic of recursive algorithms saves the day! The figure below demonstrates that moving a pile of 6 disks from Tower 1 to Tower 3 is equivalent to moving the pile of the 5 smallest disks from Tower 1 to Tower 2, then moving the 6th disk (the largest one) from Tower 1 to Tower 3, and finish by moving the 5 disks pile from Tower 2 to Tower 3.

Figure 5: Solving “Hanoi Towers” with 6 disks by solving the 5-disks case

With the same reasoning, moving the pile of 5 disks from Tower 1 to Tower 2 is equivalent to moving a pile of 4 disks from Tower 1 to Tower 3, then moving the 5th disk from Tower 1 to Tower 2, and finally moving the pile of 4 disks from Tower 3 to Tower 2. And so on until we have only the 1st disk to move (the smallest one) from Tower A to Tower B., which is trivial.

Let’s now write HanoiTowers. This function shall return a list of moves: a move is a couple (a, b) meaning “from tower a to tower b”, and list is an ordered set of moves [(a, b), (c, d), …]. Note that the operation “+” allows the concatenation of two lists.

def HanoiTowers (start_tower, finish_tower, third_tower, disks_number)

??????????????if disks_number == 1: return [(start_tower, finish_tower)] ???????# One disk => one move

??????????????else: 

                	first_move_top_disks = HanoiTowers (start, third, finish, disks_number – 1)
                
                	move_nth_disk = [(start, finish)]
                
                	second_move_top_disks = HanoiTowers (third, finish, start, disks_number - 1)
                
                	return first_move_top_disks + move_nth_disk + second_move_top_disks        

To solve the game for 6 disks, just call the HanoiTower function with start = Tower 1, finish = Tower 3, third = Tower 2, and disks_number = 6. So simple…

It was a good warm up, wasn’t it? Let’s now consider a more complex problem: the French game “Compte est bon”. Given a number to reach (let’s call it the target number), the player is given 6 numbers on which he can apply any of the +, -, / and * operations. Each of the 6 numbers can be used only once. For example, given the target 235 and the numbers 6, 2, 10, 9, 5, 7 a solution would be:

Figure 6: Example of “Compte est bon” with 6 numbers

We want to write a function CompteEstBon that takes as input the target number and the 6 numbers to be used and returns the list of operations that allows to compute the target number (if possible).

Once again, this doesn’t look like an easy task! Is it possible to find a recursive algorithm to solve it? To do that, let’s assume that we want to find a solution given a first operation (6 * 5 = 30 for example). For this, we need to solve “Compte est bon” with 5 numbers instead of 6! (Numbers 2, 10, 9 and 7 that have not been used + the new calculated number 30). See the figure below for illustration.

Figure 7: Given a first operation, reduction of a 6-numbers “Compte est bon”?to a 5-numbers one

That been said, solving “Compte est bon” problem with N numbers (size N) can be done by solving “Compte est bon” problem with N-1 numbers (size N-1) for each possible first operation: we got our recursive function! Let’s write it down using our pseudo-code. The CompteEstBon function takes as input the target number and and N numbers to be used, and returns two information:

• A Boolean value (True, False) indicating if there is a solution to the problem.
• The list of operations, for example [(6, +, 4), (7, +, 8), (15, *, 10)] to solve the problem (empty list if there is no solution).

def CompteEstBon (target, list_of_numbers):

    list_of_numbers_length = len (list_of_numbers)
 
    if list_of_numbers_length == 1:
        
       result = number_list[0]
        
       if result = target: return True, []?????????????# Only number left in list equals the target
        
       else: return False, [] 
          
    else:
          
       for each possible operation (number_1, operator, number_2):? # 6, +, 4 for ex.
          
          new_number = calculate (number_1, operator, number_2)
          
          if new_number == target: return True, [(number_1, operator, number_2)]
          
          else:
          
            sub_list_of_numbers = list_of_numbers – {number_1} – {number_2} + {new_number}
            
            sub_target_reached, sub_operations = CompteEstBon (target, sub_list_of_numbers)
            
            if sub_target_reached: return True, [number_1 operator number_2] + sub_operations
            
    return False, []????????????????# all combinations have been explored unsuccessfully:        

Another beautiful example of the power of recursive algorithms, right?

Next week I will present the concept of dynamic programming and we will explore a few examples together. Thanks for reading my post and see you next week.

?