Deep Dive Into Recursion in Swift

Most developers would agree that recursion is a non-trivial task, especially when coming from object-oriented background. The good news is that recursion can be effectively mastered if studied from the basics. In this article let’s take a look at recursion in Swift, covering computer science fundamentals along the way.

Defining Recursion

Recursion means different things when applied either to procedure or computational process.

Computational process is a series of preemptive acts performed by a program in response to user input. Simply put, it is the behavior of your program. The global process, produced by the app, consists from smaller ones, which are defined by procedures. Procedure is a pattern for the local evolution of a computational process.

Procedure is recursive if it syntactically refers (either directly or indirectly) to itself.

Computational process is recursive if its evolution pattern reveals the shape of expansion followed by contraction. It has nothing to do with a syntax of how a procedure is written.

Recursive and Iterative Processes

Procedures create two kinds of processes: recursive and iterative. In its turn, the recursive process can be of linear and tree form.

Let’s examine both kinds of processes by using the traditional factorial example. The factorial function is defined as follows:

This equation almost directly translates into Swift:

func factorial(_ n: Int) -> Int {
    if n == 1 {
        return 1
    } else {
        return n * factorial(n - 1)
    }
}

To see the evolution of the process, produced by factorial procedure, let’s examine how 5! is calculated:

factorial(5)
(5 ⋅ factorial(4))
(5 ⋅ (4 ⋅ factorial(3)))
(5 ⋅ (4 ⋅ (3 ⋅ factorial(2))))
(5 ⋅ (4 ⋅ (3 ⋅ (2 ⋅ factorial(1)))))
(5 ⋅ (4 ⋅ (3 ⋅ (2 ⋅ 1))))
(5 ⋅ (4 ⋅ (3 ⋅ 2)))
(5 ⋅ (4 ⋅ 6))
(5 ⋅ 24)
120

Now let’s approach the issue from another perspective. Computing n! can be described that first we multiple 1 by 2, then the result by 3 and proceed like this until n is reached. We can guarantee that when we reach n, the product equals to n!. Let’s reshape our description into Swift:

func factorial(_ n: Int) -> Int {
    func iter(product: Int, counter: Int) -> Int {
        if counter > n {
            return product
        }
        return iter(product: counter * product, counter: counter + 1)
    }
    
    return iter(product: 1, counter: 1)
}

As before, let’s visualize the process:

factorial(5)
iter(1, 1)
iter(1, 2)
iter(2, 3)
iter(6, 4)
iter(24, 5)
120

Although both processes calculate the same function, have the same number of steps and obtain the same result, they evolve differently. The first process expands as the chain of deferred operations is created. It is followed by contraction when the multiplication is performed. Such process is called a linear recursive process.

When looking at the second example, you clearly spot the difference. Each step of the process is completely described by a limited number of state variables and a fixed rule which describes how one step transitions to the other, and a termination condition. Since the number of steps of such process grows linearly with n, it is called a linear iterative process.

Strikingly, both procedures are recursive, although the processes they generate are not.

Memory Space Consumption

When a program is compiled and run, the information about what it is doing is captured in a special data structure named a call stack. Individual procedure calls are pushed on top of the call stack and are named stack frames. Stack frame contains the arguments passed to the procedure, the local variables of the procedure, and the address to return to after the procedure call finishes [1].

As the recursive process expands, the stack frames keep accumulating in the call stack. That consumes the amount of memory which grows with the number of the procedure calls. On the contrast, iterative processes are executed in a constant space.

Tail Recursion

Tail recursion is another name for recursive procedure which generates iterative process. Our second factorial implementation is an example of such. You must have noticed that iter(product:,counter:) could be easily re-written using for or while looping construct. According to LLVM docs, Swift compiler optimizes tail recursion and executes such procedures in a constant space.

Tree Recursion

Recursive procedure that makes more than one self-call is named tree recursive. Let’s demonstrate the idea by implementing Fibonacci numbers calculation. It has a simple solution using recursive procedure, which holds the following rules:

It is almost directly translates into Swift:

func fib(_ n: Int) -> Int {
    if n == 0 {
        return 0
    } else if n == 1 {
        return 1
    } else {
        return fib(n - 1) + fib(n - 2)
    }
}

The flow of computing fibonacci(5) has a shape of a tree:

You’ll immediately notice a problem with this implementation: fibonacci(3) is calculated twice, which is extremely inefficient. This does not mean that tree recursion is unpractical. Although it is almost useless when operating on numbers, tree recursion is a natural way of processing hierarchical data structures like graphs.

Wrapping Up

Swift programs are often written on the edge of object-oriented and functional programming paradigms. Recursion is the primary tool of the latter and Swift provides a great way to apply it in practice.

Should we use recursion regularly in iOS and macOS development?

I’d say it depends. Most of the time you can get away with higher order functions and looping constructs.

Should we know what recursion is and how it is implement and applied in Swift?

The answer is definitely yes. This article is here to help.

Further Reading

This article has been heavily inspired by Structure and Interpretation of Computer Programs. I recommend this book to everyone, who enjoys functional programming. And it is completely free.