W2222 Recursion
Background[edit]
- Recursion (Wikipedia)
- Factorial (Wikipedia) Read only until the section "Number Theory", exclusive
- Fibonacci Number (Wikipedia) Read only until the section "Mathematics", exclusive
- What on Earth is Recursion? (YouTube - Computerphile)
Introduction[edit]
Recursion is a very common topic within computer science and often one of the most confusing to understand. The Basic premise of recursion is having a function that executes over and over again until some base condition is met and the problem is solvable. Many forms of sorts, traversals, and searches rely on the usage of Recursive functions and it will be a concept you should be familiar with.
Concept of Recursion[edit]
The idea behind recursion is that a recursive function essentially breaks up a given problem into several smaller problems which can be more easily solved. Therefore, a recursive function will call itself until the given problem is easy enough to solve and the several small solutions can be used together to solve the larger problem.
Most recursive functions have essentially two sections. There's the base case and the recursive step. The recursive step is where the function will call itself again, often with some modified data, while the base case is where a developer tells the program what is that small enough problem that can be solved immediately. In other words, the base case is where the function no longer needs to break down the problem.
Let's look at this with a simple Recursive function. All we'll do is make a function called printReverse, this will return a String that counts down from a given number so the function call countDown(5) will return "5 4 3 2 1" Note that this function can be implemented with iteration as well, and while recursion should generally not be seen as a counterpart to iteration as they function differently, for the sake of demonstration we'll start here and later move onto more recursive specific examples.
String{
if(int == 1){
return "1"
}
else{
let string = String(int)
return string + " " + countDown(int: int-1)
}
}
print(countDown(int: 5))
Notice the base case. We state that if our given number is 1, we can simply return that number and essentially tell the recursive function to stop calling itself.
Let's walk through the function step by step. We've been given the integer 5, this does not equal 1 so we move to the "else" block. We make a string "5" and return this with a recursive call with the parameter 4, the same process occurs and we return "4" as a string and call the function again with the parameter 3. This keeps happening until we get 1 and we simply return 1, thus having returned 5 4 3 2 1.
If you're still confused, consult the image or try breaking the function down yourself with pen and paper.
However, keep in mind with recursive functions that it is very easy to accidentally cause the function to keep calling itself infinitely. The base case must be one that will be attained by whatever logic the recursive step is using. This is a great area for the use of preconditions.
Quiz[edit]
Usages[edit]
There are several usages of Recursive Functions. The ability to break down a problem into smaller steps can provide some very quick algorithms and patterns of solving a given problem. We'll be going through two of the most famous applications of Recursion in the following.
To Begin, let's tackle the famous print Fibonacci. Essentially the goal is to print the fibonacci number at the parameter n. The Fibonacci numbers are simply 1, 1, 2, 3, 5, 8, 13 etc. where the next number is the sum of the prior two. Therefore the call fib(5) will return 8, fib(6) will return 13 and so on. To do this, you'll need to do some more complex logic prior to the recursive step. Try solving this on your own first and then look at the solution.
func fib(int: Int) -> Int {
if(int <= 1){
return 1
}
else{
return fib(int: int-1) + fib(int: int-2)
}
}
This may have taken you a while, but it's pretty simple when you understand the base case. All we have to do here is call the function again twice in the recursive step, this will get the two fib numbers that came before the number you are looking for, and by adding these two numbers, you will have the desired number. And since the 0th number in the fibonacci sequence is 1, we'll want to make sure our base case reflects this.
For the call fib(6) we call fib(5) and fib(4) and add these two together. fib(5) and fib(4) will eventually be evaluated as 8 and 5, but first they'll be broken into fib(4) + fib(3) and fib(3) + fib(2). Eventually this whole call will be broken down into fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0). This can all be evaluated by our base case into 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 which equals thirteen.
Hopefully this gives you an idea of how recursion works. Simply making the problem smaller and easier to solve, and, in this case, breaking it down into simple 1 + 1.
This recursive methodology is used in several algorithms such as Tree Traversing, Merge Sorting, Complex Computations. Often these require less code and provide much less time to perform the operations.
Let's take a look at the famous Merge Sort to see how it uses Recursion to sort arrays incredibly quick. While we won't be implementing the code for this, it's good to take a look at the conceptual usage of recursion.
If you're unfamiliar, a Merge Sort operates by breaking up a given array into smaller smaller arrays and then merging them back together in the correct order. This is the exact methodology of Recursion.
In fact, the Merge Sort has two functions. MergeSort() and Merge(). The MergeSort() is responsible for breaking the array up into arrays of length 1 (the base case). Then the Merge Function is responsible for taking the pieces made by the Merge Sort and stitching them together in a sorted fashion. This allows for significant time optimizations which is why it is one of the quickest forms of the many sorting algorithms.
It's clear to see that recursion's methodology of breaking up a given problem into several smaller problems can be very useful to implement within an application. Think of the areas where you can apply this methodology and how it may contrast from other algorithms.
Quiz[edit]
Key Concepts[edit]
- The Main Concept of Recursion is to take a Problem and Break it down until it can be easily solved
- The Base Case is the point at which the problem can be easily solved
- The Recursive Step is where the function calls itself, often with a different parameter or different logic
- Infinite Recursion should be avoided by making sure the Base Case and Recursive Step work in tandem to ensure there is an end to the breaking down of the problem
Exercises[edit]
- M2222-10 Complete Merlin Mission Manager Mission M2222-10.
