Recursion: A Swift story about recursion

Recursion is simply about breaking down a problem.

To follow this Medium post you would need some basic Swift knowledge (functions, types and arrays) and be ready to understand one of the most important programming concepts to take your understanding of Swift to the next level.

A video has been prepared to accompany this video: https://youtu.be/WhdJbN584-o — so why not give it a look?

What is recursion?

Image for post
Image for post
What’s going on over there? What’s in the box?

Recursion a function that calls itself. if we think of the image above there are ever repeating images. But are they repeating to infinity… an image represented by a fraction of an atom(we better hope not, as we could assume the price of infinite storage would be infinity).

To stop us needing to have to split atoms to make a picture, we decide to stop at one point. This is called a base case. The base case for this image might be a single pixel on your computer screen, at which time we stop.

We can have some fun with this:

How would you tell a computer to see if someone is a descendant of GhengisKhan? Perhaps the algorithm to define who is and isn’t a descendant of GhengisKhan would look like this:

The person is an heir to Ghengis Khan if his/her father is named Ghengis Khan, or his/her father or mother is an heir to Ghengis Khan.

A quick exercise: How can you tell if you are an heir? What would you need to do, and what would this process involve?

A toy problem

Iteratively we can write out the solution:

with this simple trace table explaining the logic for countDown(2)

Image for post
Image for post

We also have a recursive version for comparison. Note how the function calls itself.

If the user ran the recursive code with countDown(2), we keep executing count down until we hit the base case of num < 1. This base case means we know when to stop.

The base case here is the following line:

if (num < 1) {return}

Giving us the following execution steps:

Image for post
Image for post
Execution steps of countDown when given the parameter 2
Image for post
Image for post

Here we can see what is happening. We only print the number for the current execution if the parameter is larger than 1. When it is less, the execution stops. The diagram to the left represents the call stack. When a program calls a recursive function, it goes to the top of the call stack (meaning it will function on a last in, first out principle).

This will become clear through later examples.

Factorials

Factorials are the product of an integer and all the integers below it; for example the factorial of four ( 4! ) is equal to 24 (since 24 = 4 * 3 * 2 * 1 ).

We can imagine that the factorial of 4 can be obtained by calculating the factorial of 3, and then times by 4. 3! = 3 * 2! and 2! = 2 * 1! and finally 1! =1

4! = 4 * 3!

3! = 3 * 2!

2! = 2 * 1!

1! = 1

This can be programmed through an iterative method. It works by looping through all of the whole numbers before (and including) num, and multiplying the result by it.

The dry run is as follows

Image for post
Image for post

Perhaps the best way of representing this is with a forwards and backwards pass through the recursive steps

Image for post
Image for post

Fibonacci sequence

Perhaps the most common example on websites and blogs is the Fibonacci sequence, which begins with the first few numbers

0, 1, 1, 2, 3, 5, 8, 13, 21, 34…

The sequence is made up of numbers that sum the two numbers that immediately precede that number. To start the series, the Fibonacci sequence starts with the numbers 0, 1.

Third number: 0 + 1 = 1

Forth number: 1 + 1 = 2

Fifth number: 2 + 1 = 3

Sixth number: 2 + 3 = 5

and so the sequence continues.

The iterative version of the fibonacci algorithm is as follows (note I’ve added the swifty guard statement in here instead of the check I’ve used above):

This looks exceedingly like the factorial sequence above, and the execution is also similar:

This is commonly represented as a recursion tree

Image for post
Image for post
A recursion tree for fib(4)

Where we can see fib(4) is made up (directly) from fib(3) and fib(2).

This is fine — but we can see that there are many repeated calls to fib(2) and fib(1).

There is a technique for minimizing these calls — dynamic programming.

This is something I will cover in a later post.

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