Working with Recursive Algorithms in Swift

By Aasif Khan | December 22, 2021 2:41 pm  | 4-min read

A recursive function is a function that calls itself. It’s an intriguing approach to solve specific coding challenges. In this tutorial, you’ll learn how to work with recursion in Swift.

Here’s what we’ll get into:

• What is recursion and how does it work?
• Useful applications of recursion
• Why it’s smart to stop the recursive function
• How recursion is especially suitable for certain problems

What Is Recursion?

The word recursion means “a repeated application of a recursive procedure or definition” – and that’s a recursion itself! In essence, a recursion happens when a thing is defined in terms of itself or its type. And in Swift, recursion means that a function calls itself!

Let’s take a look at an example:

func sum(_ numbers: [Int]) -> Int
{
guard !numbers.isEmpty else {
return 0
}

return numbers.first! + sum(Array(numbers.dropFirst()))
}

let result = sum([1, 2, 3])
print(result)

The above function sum(_:) calculates the sum of an array of integers by using recursion. The function takes an array of integers as input, and returns an integer as output. The key aspect of the function is that it calls itself! Can you spot where?

How does the sum(_:) function work? Here’s how:

• First, at the top of the function, we’re using the guard statement to check that the numbers array is not empty. When the array is empty, the function returns 0. As you’ll soon see, stopping the “loop” at the right time is an essential aspect of recursion!
• Then, the function returns a value: the first number in the array plus the sum of the remaining numbers in the array (the “tail”). This is where the recursion happens!

The head of an array is its first item. The tail of a sequence, is the array minus its head – so the remaining items. Think of it like a snake!

Let’s dive into the syntax some more. First, the return statement:

return numbers.first! + sum(Array(numbers.dropFirst()))

The first property on the numbers array contains the first value in the array. We’re force-unwrapping this value, because it’s an optional. We’re certain that the array is not empty, so it’s OK to use force-unwrapping here.

Then, the numbers.dropFirst() call will return a subsequence of a the numbers array without the first item, hence “drop first”. We’re providing that subsequence to the Array() initializer, so we’ll turn the subsequence into an array again. This array is then provided to the sum(_:) function, as its only parameter.

In short, we’re adding the first item of the array and the sum of the tail of the array. The recursion happens in calling sum(_:) for the tail of the array repeatedly, while repeatedly dropping the first item of the array. This effectively keeps adding the first array item to the rest of the array. And you ultimately end up with 1 + 2 + 3!

There’s more than one way to skin a cat – in programming too! It might have been simpler to use a for loop to create a sum of integers, but that’s not the point here. As you’ll soon see, recursion sometimes elegantly solves a programming problem that other approaches cannot.

Recursion: Does It Ever End!?

If you draw a comparison between recursion and loops, you’ll see that a recursive function typically iterates or “loops over” values by calling itself. The function calls itself, calls itself, calls itself, etcetera, and in every call, it returns a value to the caller. The loop nests deeper and deeper, until… yeah, until what!?

If you don’t terminate a recursive loop, you’ll easily create what’s known as an infinite loop. The recursion never stops, and keeps looping forever. And that isn’t very useful, right?

In sum(_:) function, the following block of Swift code will stop the recursion:

guard !numbers.isEmpty else {
return 0
}

When the input array is empty, the guard statement invokes its else clause and returns 0. This early return will prevent the function from calling itself in the subsequent line of code (see example), and stops the recursion as a result.

Every recursive function needs a way to escape the iteration. In the sum(_:) function, it’s logical to terminate the recursion when the numbers array is empty. After all, when it’s empty, there aren’t any more numbers to add, so we return 0. This prevents another, deeper sum(_:) call.

The last recursive function call to sum(_:) will be an empty array, because we’re calling dropFirst() and the before-last array has only one item. That last function call needs to return a value, because it’s added to the sum, so we return 0. But most importantly, we prevent sum(_:) from being called again, and break the recursion.

The Beauty Of Recursion

You might wonder: “Why use recursion at all?” After all, we could have easily calculated the sum of an array of integers like this:

let numbers = [1, 2, 3]
var sum = 0

for n in numbers {
sum += n
}

print(numbers)

This way of getting the sum of an array is simpler, easier to read, and about as elegant. What do you need recursion for?

As it turns out, there are specific problems in mathematics and programming that are easier to solve with recursion. Consider, for example, that you need to measure all branches of a tree, but you don’t know how many sub-branches each branch has.

You could use recursion to dive into each branch, and its sub-branches, and its sub-branches, etcetera, to add up the sum of every branch. This is impossible with a for loop without knowing the exact number of branches.

Likewise, a search algorithm called binary search uses a simple approach to find an item in a sorted array. With each recursive pass, the array is cut in half, because the algorithm has figured out in which of the two halves the to-be-found item is.

And of course, you can use recursion for the sheer fun and beauty of it. Here, check out this recursive function to calculate any n-th Fibonacci number.

func fibonacci(_ i: Int) -> Int
{
if i <= 2 { return 1 } return fibonacci(i - 1) + fibonacci(i - 2) } print(fibonacci(8)) The Fibonacci numbers are a sequence in which any number is the sum of the two preceding numbers. The sequence starts at 1, 1 (or 0, 1), so the first few numbers are: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 You can clearly see that the fifth number 5 is the result of 2 + 3, and 13 is the result of 8 + 5. We could create an intricate for in loop with several temporary values, but it’s much easier to comprehensively describe the Fibonacci sequence by using recursion. The fibonacci(_:) function will return the Fibonacci number for the given sequence number, or index, so fibonacci(8) returns 21. The function considers 1, 1 as the first two Fibonacci numbers. First, the recursion itself happens like this: return fibonacci(i - 1) + fibonacci(i - 2) Differently said, add the previous Fibonacci number and the Fibonacci number before that, and return the result. You can see how this spirals into more recursion, because the subsequent fibonacci(_:) calls will start looking for earlier Fibonacci numbers to get to the end result. Speaking of the end, that happens when we reach this bit of code: if i <= 2 { return 1 } We’re ending the recursion by not making a subsequent call to the recursive function, just as with sum(_:). By returning early, the fibonacci(_:) functions aren’t called again. And when does that happen? For the first two Fibonacci sequence numbers, 1 and 2, for which the result is 1. Neat!

Further Reading

Recursion in Swift. A function that calls itself. Now you know! It’s a useful, fun approach to looping over data, and to solve challenges. Why don’t you see if you can put it to use in your next iOS project or Swift challenge?

Create Your App Now