# 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.

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