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