Recursion: What Is It?
Recursion is simply about breaking down a problem. This article seeks to explain the concept, and how it might improve your programming!
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.
What is recursion?
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
We want to count down from the any number a user gives, down to 1. Why? To illustrate recursion (sorry, we need a simple problem before we move on).
Iteratively we can write out the solution:
with this simple trace table explaining the logic for countDown(2)
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:
Execution steps of countDown when given the parameter 2
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 above 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
Perhaps the best way of representing this is with a forwards and backwards pass through the recursive steps
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:
This looks exceedingly like the factorial sequence above, and the execution is also similar:
This is commonly represented as a recursion tree
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 minimising these calls — dynamic programming.
Disadvantages
Please bear in mind that when pursuing a recursive solution you do not know at the outset how much memory you will use, and that recursive solutions can be harder to understand (in some situations, and depending on who is attempting to understand).
There are a set of teaching materials to accompany this post: https://www.teacherspayteachers.com/Product/Recursion-and-Recursive-techniques-in-computing-and-computer-science-4358464