Recursively thinking about... recursion

Welcome back to another article

This time we'll be looking at one of those foundational concepts in Computer Science which you already know which one it is by the title.

So let's get started with it, shall we?

Some background

When we think about recursion, what are the first things that come to mind?

They might be thoughts about recursion which means that we're thinking about recursion and then... shucks here we go again.

We're now inside the recursion loop lol.

Ahhh... recursion, that concept you can define by referencing it on its own definition and still be able to get away with it.

I remember that when I was taught about it in college it was quite hard to grasp and it took me a long while to understand it.

That was mostly because of the previous course I took called "Basic Imperative Programming".

It made me get too used to think in terms of how a program should behave instead of thinking about what it has to do.

That mindset shift of "just tell the program what it has to do and it'll surely find a better way of doing it than you" was liberating and mind-expanding.

And you'll probably be like "you haven't said what Recursion actually is"

That's right my friend, I was hoping the previous image was enough hahaha.

All jokes aside, Recursion in simple terms is. A way to solve problems in which you specify the initial "base case(s)" and then what to do when those cases don't match.

So it'll be like solving a complex problem by breaking it down into smaller problems.

Then you solve those ones so that a solution can be made from all the other little ones.

Let's see it in a more practical way.

But before we do that, this post needs the obligatory XKCD image of recursion to be complete.

Alright, we may now proceed.

Recursion examples

Two of the most well-known and classic examples of recursion are the Factorial and the Fibonacci Sequence.

Factorial

You may recall that the factorial of a number is written with an exclamation mark after the number like 5! and the result can be expressed like.

$$5! = 5 x 4 x 3 x 2 x 1$$

So what would be the factorial of 8? Simply as 8 times the factorial of 7 or

$$8! = 8 x 7!$$

And we could go on and on until we're looking for the factorial of 1 which is none other than the 1 itself.

So there we have it, the factorial of a number is that number times the factorial of the previous number.

We could express that like.

$$factorial(n) = n * factorial(n - 1)$$

And we now can take that mathematical function and use it to make a program that can compute the factorial of any number we want.

factorial :: Integer -> Integer
factorial 1 = 1
factorial n = n * factorial(n-1)

The function takes an integer number and returns the value of the factorial of that number (another integer number)

So for the original example we mentioned, the factorial of 8 is 40320 which is 8 times the factorial of 7.

Fibonacci Sequence

This is another great example which if you recall from your math classes, it's a series of numbers where each number is the sum of the previous two numbers.

The first 10 numbers in the sequence are...

$$fib(10) = 1, 1, 2, 3, 5, 8, 13, 21, 34, 55$$

Now you can see that the first two numbers are actually a 1 and then they sum up to form the 2.

So if the Fibonacci of 10 is 55, we could write it as the sum of 34 plus 21 which, if you guessed it, is the Fibonacci minus 1 for the first number and minus 2 for the second number. Like so

$$fib(n) = fib(n - 1) + fib(n - 2)$$

Notice that we are using the function two times to define the result of the function which will give us another 2 functions to evaluate the result of those functions.

Have I used the word function enough times already? in case not then well... a function equals function plus function function.

How we would go about creating a program that can calculate this sequence for us?

We already know our base cases and what to do when those don't apply.

fib :: Integer -> Integer
fib 1 = 1
fib 2 = 1
fib n = fib(n-1) + fib(n-2)

There we go, now with that we can compute the values of the sequence for any number that we pass to the program.

Now, you probably were familiar with those examples already and want to see something more advanced where recursion gets more interesting.

In that case, let's look at another example that is more fun than those previous ones.

The Tower of Hanoi

This one indeed is a more interesting example. It is a game that has existed for a long time already.

It's kind of frustrating when you first encounter it and you don't have any notions of programming or maths.

Nevertheless, it's a fun game when you can actually play it with a wooden structure.

Although you can still play the game online if you want.

The objective of this game is to move all the disks from the start to the destination while using the middle rod as a temporary place.

When moving the disks you have the respect two rules.

1. You can only move one disk at a time.
2. You cannot place a larger disk on top of a smaller one (or else the weight of the bigger will crush the smaller and that's no bueno)

Only having 3 disks the solution to the problem is pretty straightforward.

We can start moving the little one to the destination then the middle one to the temporary and now we have the disks in 3 separated sticks.

From there, move the little one to the temporary place then move the large one to the destination.

Now, move the little one back to the start and the middle one to the destination.

Finally the little one there too and badabim badabom you're already done.

If you count, it only takes 7 moves to win the game with 3 disks but with 4 disks it takes 15, and for 5 it takes 31.

Now, we can extrapolate that process to solve the problem for much more disks like 10 or 25.

Using recursion, we could say that the process required to move 3 disks from point A to point C is the same process to move n-1 disks.

And the idea is that we move a smaller amount of disks solving a similar problem in every step until we get to our final solution.

We now repeat that process of moving disks until we reach the base case which is moving 1 disk. Easy right? we just pick it and move it to where it has to go.

So if you've been following along 'till this point and are thinking "yeah I get it that's easy" then it's time for action.

Let's turn our strategy of moving disks and our base case into a recursive algorithm that can solve the problem for any number of disks that we want to use.

Remember that as the number of disks increase, so does the number of steps and we'll need more time (and patience) to move that recursive load.

Now speaking of recursive load... I remembered about this comic

And to not make this post longer than it should, I'll leave it to you to implement the solution to this problem as a program that could take 3 inputs:

• the number of disks (e.g. 'n')
• the label of the starting point (e.g. 'A')
• the label of the destination point (e.g. 'C')

The program should output the sequence of steps required to move the n disks from the A point to the C point.

---

Well, that's it for this post. Thanks for reading so far.

If you want, post your solution in the comments or reach out and let me know how would you implement it.

Thanks again and hope to see you on the next one!

Comments

[John Peters]

Nice post Thanks!

I worked for a company whose tech lead did not allow recursion of any type! He must have had a nightmare once that permanently scared him. Talking about PTSD.