Recursion is one of the most used techniques in FP and it 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 the following:

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 return1 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(repeatString(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.