- Write recursive functions to solve problems
- Use dynamic programming to improve runtime efficiency
In computer science, recursion basically means a function that calls itself. Recursion can be a little mind bending at first but is actually relatively simple: it's basically just another way to create loops.
In fact, anything that can be done iteratively with a for loop or while loop can also be solved with recursion, and vice versa. There are some languages (like Haskell) that do not even have iterative forloops or while loops at all, and use recursion for all looping instead!
A recursive function consists of two things:
- A recursive call
- A base case
A recursive function is a function that calls iteself.
func recurse() {
print("hi")
recurse()
}recurse() is a recursive function. It will print "hi", then call itself, which will print "hi" and then call itself, which will print "hi" and then call itself, and so on.
Recursive Patrick
How can we stop this process and have it do something more useful?
The most important part of any recursive function is the 'base case'. The base case is basically a conditional that tells the function to stop calling itself (the base case is usually just a simple if statement):
The function should NOT call itself within the base case. In other words, the base case if statement should do the very last thing the function does before ending.
Here's another example of a recursive function without a base case:
func countDownToZero(from num: Int) {
print(num)
countDown(from: num - 1)
}When do we want this function to stop running?
When num is zeroLet's add that base case:
func countDownToZero(from currentNum: Int) {
if currentNum == 0 {
return
}
print(currentNum)
countDownToZero(from: currentNum - 1)
}Make sure your recursive functions always have a base case!
Even though we added a base case to our countDownToZero function above, it still has the possibility to run forever.
For what input to countDownToZero(from:) will run forever?
If the input is less than zero.How can we resole this issue
func countDownToZero(from currentNum: Int) {
if currentNum <= 0 {
return
}
print(currentNum)
countDownToZero(from: currentNum - 1)
}Write a function that counts up to a target number.
func countUp(to target: Int, startingAt currentNum: Int) {
}We just saw an example of how to write a loop recursively.
We could have done that iteratively pretty easily:
func countUp(to target: Int, startingAt currentNun: Int) {
for i in currentNum...target {
print(i)
}
}Anything that we can solve iteratively, we can solve recurseively and vice versa.
This leads to a natural question. If recursion looks more confusing, why would we ever want to use it solve problems?
In general, you should only use recursion if it would be significantly simpler than the iterative solution. A good rule of thumb is to use recursion when it helps makes your code more readable. In most cases iterative solutions are preferable over recursive solutions because recursion has some added performance costs, like extra function calls.
One simple example of how to practically use recursion is with the factorial algorithm.
Factorial (symbol: "!") means to multiply a integer by every integer before it.
Example: 5! = 5 * 4 * 3 * 2 * 1 = 120
Let's make an iterative solution first, then let's compare it to a recursive solution:
Iterative factorial
func factorial(n: Int) -> Int {
var product = 1
for currentNum in 1...n {
product *= currentNum
}
return product
}Recursive Factorial
func recursiveFactorial(n: Int) -> Int {
guard n > 1 else {return 1} //Base Case
return n * recursiveFactorial(n: n - 1) //Recursive Call
}A common, real world example of when to use recursion is the Fibonacci sequence. Here is the recursive solution for finding the nth number of a Fibonacci sequence:
The Fibonacci sequence is made by adding the two previous numbers together:
1, 1, 2, 3, 5, 8, 13, 21, 34 ...
Recursive Fibonacci
func recursiveFib(n: Int) -> Int {
guard n > 2 else { return 1 }
return recursiveFib(n: n - 1) + recursiveFib(n: n - 2)
}The advantage of recursive solutions is that they can be much easier to understand. This code is very dense, so we should take a look at what it's doing.
Visual Representation
With stick figures
What might be a downside of using this method?
It's very slow! We have to do a lot of the same work over again.
Memoization
In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
Dynamic Programming is the combination of Memoization and recursion. We can work memoization into our recursive Fibonacci to improve the runtime.
var fibValues = [Int: Int]()
func recursiveFibDynamicProgramming(num: Int) -> Int {
if let fibonacci = fibValues[num] {
return fibonacci
}
guard num > 2 else {
return 1
}
let fibonacci = recursiveFibDynamicProgramming(num: num - 1) + recursiveFibDynamicProgramming(num: num - 2)
fibValues[num] = fibonacci
return fibonacci
}In iterative loops, we count the number of loops in order to figure out the Big O complexity. Similarly, with recursion, we count the number of times the function is being called.
In recursive functions, state is passed down through arguments. In other words, you should generally not save variables within your recursive functions. Instead, if you want to keep track of any data, you should pass them down through arguments. In this way the function's arguments basically keep a history of the state of the function. This makes recursive functions immutable, which is one of their advantages.
Pair Programming exercises
Recursion Exercises