Working With Recursive Algorithms In Swift

Written by Reinder de Vries on September 10 2019 in App Development

Working With Recursive Algorithms In Swift

A recursive function is a function that calls itself. It’s an intriguing approach to solve specific coding challenges. In this article, 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

Ready? Let’s go.

  1. What Is Recursion?
  2. Recursion: Does It Ever End?
  3. The Beauty Of Recursion
  4. Further Reading

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, this is a crucial aspect of recursion!
  • Then, the function returns a value. It returns 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 actual array again. This array is then fed into the sum(_:) function again.

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!

Learn how to build iOS apps

Get started with iOS 13 and Swift 5

Sign up for my iOS development course, and learn how to build great iOS 13 apps with Swift 5 and Xcode 11.

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 terminates the recursion as a result.

Every recursive function needs an escape. 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.

The last recursive function call to sum(_:) will be an empty array, because the before last array has only one item, and we’re calling dropFirst(). That last function call needs to return something, 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 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.

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!

Learn how to build iOS apps

Get started with iOS 13 and Swift 5

Sign up for my iOS development course, and learn how to build great iOS 13 apps with Swift 5 and Xcode 11.

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?

Want to learn more? Check out these resources:

Reinder de Vries

Reinder de Vries

Reinder de Vries is a professional iOS developer. He teaches app developers how to build their own apps at LearnAppMaking.com. Since 2009 he has developed a few dozen apps for iOS, worked for global brands and lead development at several startups. When he’s not coding, he enjoys strong espresso and traveling.