Understanding and implementing a recursive binary search in swift

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.

Recursion is a concept of calling 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 the base

The kill switch is very important in a recursive function just like how a switch is very important for every 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 we don't want that.

Recursive function example:

The example below is a simple recursive function that takes in a value n then calculates and return the factorial of that value n using the factorial formula (n! = n * (n - 1)!) for n > 1

func factorial(of n: Int) -> Int {

    if n <= 1 { // The kill switch
        return 1
    } else {
        return n * factorail(of: n - 1)
    }
}
// The 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 1.

// Testing our factorial function

let factFive = factorial(of: 5)
print(factFive)

120

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

Remember the concepts behind a typical binary search function is that we need to keep track of three different variables which are left right and middle and that our items must but sorted

Before We proceed if you don't understand how binary search works I suggest you take a look at the previous post on binary search here

Recursive Binary Search

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 are used to calculate the middle of an array to the function itself since we no longer have a loop to help us update their values each time, just like usual.

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

func recursiveBinarySearch(for value: Int, in items: [Int], left: Int, right: Int) -> Int? {
    var mid = (left + right) / 2
    
    if left > right { // kill switch: Return from function whenerve the two indexes intesects
        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!

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 { // kill switch: Return from function whenerve the two indexes intesects
        return nil
        
    } else if items[mid] == value {
        return mid
        
    }
}

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 { // kill switch: Return from function whenerve the two indexes intesects
        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)
    }
}

Testing our binary search 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")
}

Index is : 6 for value: 30

value: -50 is not in numbers

The diagram below shows how the function updates left and right during each call.

Recursive Binary search diagram

This marks the end of this tutorial thanks for reading! I hope it wasn't boring for you as I tried to make it as fun as possible. Please report any typos and questions and I will gladly follow up