During Computer Science class one of the students asked the teacher:
-How can we understand what is the recursion?
The teacher was thinking for a few seconds and said:
-To understand recursion you need to understand what is the recursion.
-…. what?
Recursion is a different approach to solve some problems. Sometimes it saves a lot of time, code and code becomes simpler than in iteration way. For example, the most popular sorting algorithm: quicksort. It uses recursion in its implementation.
How Does Recursion Work?
Let’s look at factorial. We want to calculate factorial of 5. As Wikipedia says: “Factorial […] is the product of all positive integers less than or equal to n“. And we know that factorial of 0 is 1.
Factorial will be an excellent example to use recursion.
How much is factorial of 5? It’s 5 * factorial of 4.
How much is factorial of 4? It’s 4 * factorial of 3.
How much is factorial of 3? It’s 3 * factorial of 2.
How much is factorial of 2? It’s 2 * factorial of 1.
How much is factorial of 1? It’s 1 * factorial of 0.
How much is factorial of 0? We know it’s 1.
Now, we can multiply everything and we get the result which is 120.
1 * 2 * 3 * 4 * 5 = 120
Recursion is invoking itself until we reach some condition
Recursion in Code
How to embed in one function? In this example, we could create for/while loop and multiple numbers from 1 to n. But we want to use recursion. The factorial function will invoke itself with a number smaller by 1 until it receives 0 then it returns 1 as the definition says.
func factorial(number: Int64) -> Int64 {
if number > 0 {
return number * factorial(number: number – 1)
} else {
return 1
}
}
let number: Int64 = 5
print(“Factorial of \(number) is: \(factorial(number: number))”)
Output:
Factorial of 5 is: 120
