Recursion in Swift
What is Recursion?
Recursion is defining some code structure in terms of itself. Recursive functions are functions that call themselves while recursive data is a data structure that contains an instance of itself. Why would you want to do this? In some cases, this technique allows algorithms and data structures to be expressed in a more natural and direct form. In this article, I will explain this technique and when to use it.
Structural Recursion
A data structure is recursive if within its definition it refers to itself. For example, we might define a linked list this way:
indirect enum LinkedList<Element> {
case empty
case connected(element: Element, remaining: LinkedList)
}
In Swift, the use of the indirect keyword is required when defining recursive enums. The LinkedList data structure is recursive because LinkedList is used in the definition for the remaining list in the connected case.
Another example is a binary tree:
indirect enum BinaryTree<Element> {
case empty
case branch(leftTree: BinaryTree, element: Element, rightTree: BinaryTree)
}
This data structure is also recursive because both the leftTree and rightTree in the branch case are also of type BinaryTree.
Functional Recursion
Just like structural recursion, recursive functions are functions that are defined in terms of themselves. For example:
func countdown(from value: Int) -> [Int] {
guard value >= 0 else { return [] }
return [value] + countdown(from: value - 1)
}
Notice how this function calls itself to produce the remaining elements of the array being returned.
Base Case
In both structural and functional recursion, we must provide a way for the recursion to end. This ending point is often called the base case. Without a base case, we would have an infinite data structure or a function that never returned. Both are not possible. (Infinite data structures are possible with lazy evaluation, but I’m ignoring that here since it’s not supported at the language level in Swift.) For this reason, structs in Swift cannot be directly recursive because there’s no way to include the required base case.
Code Structure from Data Structure
When defining functions to process data structures, the structure of the code produced will follow the structure of the data. For example:
extension LinkedList {
func map<Mapped>(_ transform: (Element) -> Mapped) -> LinkedList<Mapped> {
switch self {
case .empty:
return .empty
case let .connected(element, remaining):
let newElement = transform(element)
return .connected(element: newElement, remaining: remaining.map(transform))
}
}
}
Because the type of self here is an enum, we must switch on it to find out which case we’re in, and because this enum is recursive it is quite natural to write this function recursively. (This isn’t a very good idea in this case because it unnecessarily uses linear space.) The match in structure from data to code applies to the BinaryTree data structure as well.
extension BinaryTree {
func map<Mapped>(_ transform: (Element) -> Mapped) -> BinaryTree<Mapped> {
switch self {
case .empty:
return .empty
case let .branch(leftTree, element, rightTree):
let newElement = transform(element)
return .branch(
leftTree: leftTree.map(transform),
element: newElement,
rightTree: rightTree.map(transform)
)
}
}
}
With BinaryTree this recursive solution is fine since the maximum depth of recursion in logarithmic to the size of the tree. (Assuming the tree is balanced.)
Generative Recursion
In some problems, the data being recursed over is not stored in the data structure but must be produced as you go. So rather than just following the recursive structure of the data, the recursive function must produce new data and pass it along in the recursive call. For example, consider this recursive algorithm for finding the greatest common divisor of two numbers:
func gcd(_ num1: Int, _ num2: Int) -> Int {
if num2 == 0 {
return num1
}
else {
return gcd(num2, num1 % num2)
}
}
This recursion is generative because on each recursive call, num1 % num2 is being computed and the passed on in the recursive call.
Generative recursion is a bit harder to reason about because it can be hard to prove that it will always get to a base case and stop recursing.
Tail Call Optimization
Recursive functions can be a bit dangerous because, on each successive recursive call, a new stack frame is created to store the parameters and local variables of the function. The stack has a limited size and if exceeded, will result in a runtime crash, but there exists a technique to stop stack frames from being produced needlessly. Tail call optimization is an optimization strategy used by some compilers to do just that.
To take advantage of this optimization we must write our recursive functions in tall call form. Tail call form is where the very last operation performed by the function on the recursive branch is the recursive call. That is that after the recursive call returns, the calling function has no more work to do and simply returns the same result directly. Let’s walk through an example. This first version is not in tail call form:
func factorial(of num: Int) -> Int {
if num <= 1 {
return 1
}
else {
return num * factorial(of: num - 1)
}
}
In this function, we are not in tall call form because after the recursive function call returns, we still must multiply the returned value times num. This means that the value of num must be held in memory for the entire duration of the recursive call requiring that we hold on the current stack frame where it is stored.
Here’s the tail call version:
func factorial(of num: Int) -> Int {
func factorial(of num: Int, result: Int) -> Int {
guard num > 1 else {
return result
}
return factorial(of: num - 1, result: result * num)
}
return factorial(of: num, result: 1)
}
Note in this version, we add a nested function and a accumulated result. This form corresponds one-to-one to a form with a while loop.
Here’s that version:
func factorial(of num: Int) -> Int {
var result = 1
var num = num
while num > 1 {
result = result * num
num = num - 1
}
return result
}
The trampoline call to the nested function return factorial(of: num, result: 1) in the recursive version is the same as the initialization of the variables result and num in the while loop version. The while loop condition that num > 1 matches with the check for the base case in the recursive version. The mutation of result and num in the while loop is performed in the recursive version by passing new values in the recursive call to the nested function. Finally, the returning of result after the while loop pairs up with the returning of result in the recursive base case.
The Swift compiler will sometimes perform tail call optimizations. For example, compiling the non-recursive version of factorial with optimizations on produces the following assembly:
.section __TEXT,__text,regular,pure_instructions
.macosx_version_min 10, 13
.globl _main
.p2align 4, 0x90
_main:
pushq %rbp
movq %rsp, %rbp
xorl %eax, %eax
popq %rbp
retq
.private_extern __T04main9factorialS2i2of_tF
.globl __T04main9factorialS2i2of_tF
.p2align 4, 0x90
__T04main9factorialS2i2of_tF:
pushq %rbp
movq %rsp, %rbp
pushq %rbx
pushq %rax
movq %rdi, %rbx
cmpq $2, %rbx
jl LBB1_1
leaq -1(%rbx), %rdi
callq __T04main9factorialS2i2of_tF
imulq %rbx, %rax
jno LBB1_3
## InlineAsm Start
## InlineAsm End
ud2
LBB1_1:
movl $1, %eax
LBB1_3:
addq $8, %rsp
popq %rbx
popq %rbp
retq
.private_extern ___swift_reflection_version
.section __TEXT,__const
.globl ___swift_reflection_version
.weak_definition ___swift_reflection_version
.p2align 1
___swift_reflection_version:
.short 3
.no_dead_strip ___swift_reflection_version
.linker_option "-lswiftCore"
.linker_option "-lobjc"
.section __DATA,__objc_imageinfo,regular,no_dead_strip
L_OBJC_IMAGE_INFO:
.long 0
.long 1600
.subsections_via_symbols
Notice the callq __T04main9factorialS2i2of_tF instruction. This is a function call which results in a new stack frame being produced.
In contrast, the tail call version results in the following:
.section __TEXT,__text,regular,pure_instructions
.macosx_version_min 10, 13
.globl _main
.p2align 4, 0x90
_main:
pushq %rbp
movq %rsp, %rbp
xorl %eax, %eax
popq %rbp
retq
.private_extern __T03tco9factorialS2i2of_tF
.globl __T03tco9factorialS2i2of_tF
.p2align 4, 0x90
__T03tco9factorialS2i2of_tF:
pushq %rbp
movq %rsp, %rbp
movl $1, %eax
cmpq $2, %rdi
jl LBB1_3
.p2align 4, 0x90
LBB1_1:
imulq %rdi, %rax
jo LBB1_4
cmpq $2, %rdi
leaq -1(%rdi), %rdi
jg LBB1_1
LBB1_3:
popq %rbp
retq
LBB1_4:
## InlineAsm Start
## InlineAsm End
ud2
.private_extern ___swift_reflection_version
.section __TEXT,__const
.globl ___swift_reflection_version
.weak_definition ___swift_reflection_version
.p2align 1
___swift_reflection_version:
.short 3
.no_dead_strip ___swift_reflection_version
.linker_option "-lswiftCore"
.linker_option "-lobjc"
.section __DATA,__objc_imageinfo,regular,no_dead_strip
L_OBJC_IMAGE_INFO:
.long 0
.long 1600
.subsections_via_symbols
Here there are no function call instructions present thus no stack frames being produced.
When is Recursion the Right Design?
Whenever you are iterating over a recursive data structure the natural design is a recursive function, however there is a danger of a stack overflow with a large amount of data. This is greatest when the data is linear in structure like a linked list. Trees generally are safe to recurse over since the maximum depth of recursion is logarithmic to the number of elements (if the tree is balanced).
Generative recursion is a bit more dangerous because it can be harder to prove the maximum depth of recursion, but this should be balanced with code clarity.