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

`here`

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

Swift Algorithms