Recursion is the process of calling a function inside itself. The function that calls itself is a recursive function.
Recursion is best used for problems where a large problem can be broken down into a repetitive subproblem. As a recursive function calls itself to solve these subproblems, eventually the function will come across a subproblem that it can handle without calling itself. This is known as a base case, and it is needed to prevent the function from calling itself over and over again without stopping.
In the base case, the function does not call itself. However, when a function does have to call itself in order to deal with its subproblem, then this is known as a recursive case. So, there are two types of cases when using a recursive algorithm: base cases and recursive cases. It is important to remember that when using recursion and when we are trying to solve a problem, we should ask ourselves: what is my base case and what is my recursive case?
To apply this simple process, let's start with an example of recursion: the factorial function. In mathematics, an exclamation mark after a number (n!) presents the factorial of the number. A factorial of a number n is the product of all integers between 1 and n. So, if n is equal to 3, then the factorial of n would be 3 * 2 * 1, which equals 6. We could also say that the factorial of 3 is equal to 3 multiplied by the factorial of 2, which would be 3 * 2! or 3 * 2 * 1. So, the factorial of any number n could also be defined as follows:
n! = n * (n - 1)!
We also need to know the following:
0! = 1! = 1
Note how we defined the factorial of a number as that number multiplied by the factorial of the integer that is 1 less than the number (n * (n - 1)!). So, what we have done is essentially broken the problem into a subproblem and, in order to find the factorial of a number, we keep finding the factorials of the integers below that number and multiplying. So, the factorial of 3 is equal to 3 multiplied by the factorial of 2 and the factorial of 2 is equal to 2 multiplied by the factorial of 1. So, if we have a function to find the factorial of a given number, then our code for the recursive case would look something like this:
func factorial(n: Int) -> Int {
return n * factorial(n: n - 1)
}
Here, we want to find n number's factorial.
In this example, we divided the problem into a subproblem. There is still one problem that we need to solve. We need to check for the base case in order to be able to stop the function from calling itself infinitely.
Therefore, we can modify our factorial example as follows:
func factorial(n: Int) -> Int {
return n == 0 || n == 1 ? 1 : n * factorial(n: n - 1)
}
print(factorial(n: 3))
As seen in this example, we check for n; if it is 0 or 1, we return 1 and stop the recursion.
Another example of a simple recursive function is as follows:
func powerOfTwo(n: Int) -> Int {
return n == 0 ? 1 : 2 * powerOfTwo(n: n - 1)
}
let fnResult = powerOfTwo(n: 3)
The non-recursive version of this example is as follows:
func power2(n: Int) -> Int {
var y = 1
for _ in 0...n - 1 {
y *= 2
}
return y
}
let result = power2(n: 4)
As we can see from this example, the recursive version is more expressive and shorter.
The following example presents a function that repeats a given string for a desired time:
func repateString(str: String, n: Int) -> String {
return n == 0 ? "" : str + repateString(str: str , n: n - 1)
}
print(repateString(str: "Hello", n: 4))
The following code snippet presents the same functionality without using recursion, in other words, in the imperative programming style:
func repeatString(str: String, n: Int) -> String {
var ourString = ""
for _ in 1...n {
ourString += str
}
return ourString
}
print(repeatString(str: "Hello", n: 4))
The non-recursive, imperative version is slightly longer and we need to use a for loop and variable to be able to achieve the same result. Some functional programming languages such as Haskell do not have for loop mechanisms and we have to use recursion; in Swift, we have for loops but as we have seen here, it is better to use recursive functions whenever we can.
Tail recursion is a special case of recursion where the calling function does no more execution after making a recursive call to itself. In other words, a function is named tail recursive if its final expression is a recursive call. The previous recursion examples that we have been introduced to were not tail recursive functions.
To be able to understand tail recursion, we will develop the factorial function that we have developed before with the tail recursion technique. Then we will talk about the differences:
func factorial(n: Int, currentFactorial: Int = 1) -> Int {
return n == 0 ? currentFactorial : factorial(n: n - 1,
currentFactorial: currentFactorial * n)
}
print(factorial(n: 3))
Note that we provide a default argument of 1 for currentFactorial, but this only applies to the very first call of the function. When the factorial function is called recursively, the default argument is overridden with whatever value is passed by the recursive call. We need to have that second argument there because it will hold the current factorial value that we intend on passing to the function.
Let's try to understand how it works and how it is different from the other factorial function:
factorial(n: 3, currentFactorial: 1) return factorial(n: 2, currentFactorial: 1 * 3) // n = 3 return factorial(n: 1, currentFactorial: 3 * 2) // n = 2 return 6 // n = 1
In this function, each time the factorial function is called, a new value for currentFactorial is passed to the function. The function basically updates currentFactorial with each call to itself. We are able to save the current factorial value as it accepts currentFactorial as a parameter.
All of the recursive calls to the factorial such as factorial(2, 1 * 3) do not actually need to return in order to get the final value. We can see that we actually arrive at the value of 6 before any of the recursive calls actually return.
Therefore, a function is tail recursive if the final result of the recursive call—in this example, 6—is also the final result of the function itself. The non-tail recursive function is not in its final state in the last function call because all of the recursive calls leading up to the last function call must also return in order to actually come up with the final result.