Recursion is one very interesting subject in computer science. It is so interesting that the more you read about it, the more intrigued you become, and would like to learn more about the concept behind it.

What is Recursion?

Recursion is a concept of calling a function or method within itself (without a loop) over and over again until a certain condition is met, and that condition is called the kill switch or base case.

The kill Switch

The kill switch is very important in a recursive function just like how a switch is important for a light bulb because without a switch the light bulb will continue to light until it eventually dies, and without a kill switch for a recursive function it will run into an infinity loop and continues until your computer memory gets overflowed, and you wouldn’t want that.

Recursive Function Example

The example below is a simple recursive function that accepts a value n then calculates and return the factorial of that value n using the factorial formula:

func factorial(of n: Int) -> Int {
    if n <= 1 {
        return 1
    } else {
        return n * factorial(of: n - 1)
    }
}

Kill Switch

if n <= 1 {
    return 1
}

The n <= 1 is our kill Switch, the factorial of both 1 and 0 is 1 and there is no reason to call the function body again. If we didn’t implement the kill switch the function will keep calling itself forever even when n is no longer positive and this already defies the formula rule which states that n must be greater than or equal to 1.

Recursive Binary Search

In this example, I will show you how to implement a binary search function using the recursion method (there will be no loops involved).

1. Create Function

func recursiveBinarySearch(for value: Int, in items: [Int], left: Int, right: Int) -> Int? {
    var mid = (left + right) / 2
}

What we have just done above is pass the variables that will be used to calculate the middle of array to the function itself since we no longer have a loop to help us update their values each time, just as usual.

2. Add a Kill Switch

Now let’s add a kill switch so that our function will know when to stop looking for value i.e. calling itself.

func recursiveBinarySearch(for value: Int, in items: [Int], left: Int, right: Int) -> Int? {
    var mid = (left + right) / 2

    if left > right {
        return nil
    }
}

Our kill switch states that whenever the left is bigger than the Right it should stop looking for value and just return nil because our value was not found.

3. Return Found Value

The second kill switch, the else if items[mid] == value this will make sure that the function stops calling itself again when our value is found and return it.

func recursiveBinarySearch(for value: Int, in items: [Int], left: Int, right: Int) -> Int? {
    var mid = (left + right) / 2

    if left > right {
        return nil
    } else if items[mid] == value {
        return mid
    }
}

4. Recursive Call

Now let us add the complete body in charge of calling the functions for updating left and right for recalculation of middle

func recursiveBinarySearch(for value: Int, in items: [Int], left: Int, right: Int) -> Int? {
    var mid = (left + right) / 2

    if left > right {
        return nil
    } else if items[mid] == value {
        return mid
    } else if items[mid] < value {
        return recursiveBinarySearch(for: value, in: items, left: mid + 1, right: right)
    } else {
        return recursiveBinarySearch(for: value, in: items, left: left, right: mid - 1)
    }
}

Test Function

let numbers = [-2, 0, 1, 4, 10, 20, 30, 40, 50, 60, 70, 90]
let value = 30

if let index = recursiveBinarySearch(for: value, in: numbers, left: 0, right: numbers.count - 1) {
    print("Index is : \(index) for value: \(numbers[index])")
}

let valueTwo = -50

if let index = recursiveBinarySearch(for: valueTwo, in: numbers, left: 0, right: numbers.count - 1) {
    print("Index is : \(index) for value: \(numbers[index])")
} else {
    print("value: \(valueTwo) is not in numbers")
}

Conclusion

This marks the end of this tutorial on recursive binary search algorithm implementation in swift. Hope you had fun reading along, report any typos, or errors, and I will follow up.