Swift Programming from Scratch
The Swift Sandbox is integrated, making the exercises interactive. Read more about the book here.
Chapter 8: Recursion
Recursion is the process of repeating items in a self-similar way.
picture by Pavlos Mavridis
The same way you can call a function inside of other functions, you can call a function inside of itself. A function that calls itself is called a recursive function. Recursion is important because you can solve some problems by solving similar sub-problems. Recursive solutions usually have less code and are more elegant that their iterative equivalents if the problem you solve is recursive in nature.
Let’s take a simple example. To print all the numbers from 1
to N
, the first thing we have to do is print all the numbers from 1
to N-1
and then print N
.
func printFirstNumbers(_ N: Int) {
if N > 1 {
printFirstNumbers(N - 1)
}
print(N)
}
printFirstNumbers(3)
// 1
// 2
// 3
Okay … the example from above works … but what really happens?
To understand what happens we can take a look at a modified version of the printFirstNumbers
function. This version will print all the steps it takes.
func printFirstNumbers(_ N: Int) {
print("start printFirstNumbers(\(N))")
if N > 1 {
print("printFirstNumbers(\(N)) calls printFirstNumbers(\(N-1))")
printFirstNumbers(N - 1)
}
print("printFirstNumbers(\(N)) will print \(N)")
print("end printFirstNumbers(\(N))")
}
printFirstNumbers(3)
// start printFirstNumbers(3)
// printFirstNumbers(3) calls printFirstNumbers(2)
// start printFirstNumbers(2)
// printFirstNumbers(2) calls printFirstNumbers(1)
// start printFirstNumbers(1)
// printFirstNumbers(1) will print 1
// end printFirstNumbers(1)
// printFirstNumbers(2) will print 2
// end printFirstNumbers(2)
// printFirstNumbers(3) will print 3
// end printFirstNumbers(3)
The computer knows where to continue the execution of printFirstNumbers(2)
after printFirstNumbers(1)
finishes by using a data structure known as a call stack. The call stack keeps information about the currently active functions. When printFirstNumbers(1)
starts executing printFirstNumbers(3)
and printFirstNumbers(2)
are still active and they need to resume control right after the if statement.
Notice that printFirstNumbers(1)
did not call printFirstNumbers
again. That’s known as a base case. You need to have at least one base case inside a recursive function in order to prevent infinite calls – or what is known as stack overflow.
Let’s take another example. This time instead of printing the numbers from 1
to N
let’s do it from N
to 1
.
To count from N
to 1
all we need to do is print N
then print all the numbers from N-1
to 1
.
func printFrom(_ N: Int) {
print(N)
if N > 1 {
printFrom(N - 1)
}
}
printFrom(5)
// 5
// 4
// 3
// 2
// 1
You can find another example of recursion if you google recursion. The results page will ask you “Did you mean: recursion” which will take you to the same page…
Here are some visual examples of recursion. The Sierpinski triangle and carpet.
Sierpinski triangle
Sierpinski carpet
And here you can find a recursive drawing editor made by Toby Schachman. It’s super easy to use – and a lot of fun. If you didn’t understand what recursion is all about I highly encourage you to take a few minutes to play with it.
An example image that could be generated using recursive drawing
Things to remember about recursion:
- you can call a function inside of itself
- you always have at least one base case in order to prevent the function calling itself infinite times
8.1 Fibonacci
Implement a recursive function named fibonacci
that takes a number N
and returns the N
-th fibonacci number. The first two fibonacci numbers are 1
and the rest are the sum of the previous two.
func fibonacci(_ i: Int) -> Int
Function call:
fibonacci(3)
Function output:
2
Function call:
fibonacci(4)
Function output:
3
Function call:
fibonacci(5)
Function output:
5
Function call:
fibonacci(6)
Function output:
8
Remember that if N > 2
, fibonacci(N) = fibonacci(N - 1) + fibonacci(N - 2)
func fibonacci(_ i: Int) -> Int {
if i <= 2 {
return 1
} else {
return fibonacci(i - 1) + fibonacci(i - 2)
}
}
8.2 Factorial
The factorial of a non-negative integer N
, denoted N!
, is the product of all the positive integer less than or equal toN
. The value of 0!
is defined as 1
.
1! = 1
2! = 1 * 2 = 2
3! = 1 * 2 * 3 = 6
...
7! = 1 * 2 ... * 7 = 5040
Write a recursive function named factorial
that takes an integer N
and returns it’s factorial.
func factorial(_ N: Int) -> Int
Function call:
factorial(3)
Function output:
6
Function call:
factorial(5)
Function output:
120
Function call:
factorial(10)
Function output:
3628800
N! = N * (N - 1)!
func factorial(_ N: Int) -> Int {
if N == 1 {
return 1
} else {
return N * factorial(N - 1)
}
}
8.3 Digits
Implement a recursive function named digits
that takes a positive integer number
and return an array containing it’s digits in order.
func digits(_ number: Int) -> [Int]
Function call:
digits(123)
Function output:
[1, 2, 3]
Function call:
digits(0)
Function output:
[0]
Function call:
digits(54321)
Function output:
[5, 4, 3, 2, 1]
To get the digits of a number you need to get the digits of the number without its last digit (divide by 10
). And then add the last digit to that result.
func digits(_ number: Int) -> [Int] {
if number >= 10 {
let firstDigits = digits(number / 10)
let lastDigit = number % 10
return firstDigits + [lastDigit]
} else {
return [number]
}
}
8.4 Power
Write a recursive function pow
that takes two numbers x
and y
as input and returns x
to the power y
.
func pow(_ x: Int, _ y: Int) -> Int
Function call:
pow(2, 10)
Function output:
1024
Function call:
pow(3, 3)
Function output:
27
Function call:
pow(100, 1)
Function output:
100
Function call:
pow(10, 0)
Function output:
1
A simple recursive formula we can use is x^y = x * x ^ (y - 1)
Using x^y = x * x^(y-1)
:
func pow(_ x: Int, _ y: Int) -> Int {
if y == 0 {
return 1
} else {
return x * pow(x, y - 1)
}
}
Using exponentiation by squaring:
func pow(_ x: Int, _ y: Int) -> Int {
if y == 0 {
return 1
} else if y == 1 {
return x
} else {
// compute x^(y/2)
let xy2 = pow(x, y / 2)
// if y is even
if y % 2 == 0 {
// x^y is x^(y/2) squared
return xy2 * xy2
} else {
// x^y is x^(y/2) squared times x
return xy2 * xy2 * x
}
}
}
8.5 Euclid
Implement the Euclidian algorithm for getting the greatest common divisor of two numbers by using repeated subtractions. The algorithm starts with two numbers and subtracts the smallest one from the other one until one of them becomes zero, the other one is the greatest common divisor of the original number. The gcd
function takes two numbers as input and returns their greatest common divisor. Implement the algorithm as a recursive function.
Algorithm example:
10 2
8 2
6 2
4 2
2 2
2 0 // 2 is the greatest common divisor of 10 and 2
9 6
3 6
3 3
3 0 // 3 is the greatest common divisor of 9 and 6
35 49
35 14
21 14
7 14
7 7
7 0 // 7 is the greatest common divisor of 35 and 49
func gcd(_ a: Int, _ b: Int) -> Int
Function call:
gcd(2, 10)
Function output:
2
Function call:
gcd(9, 6)
Function output:
3
Function call:
gcd(30, 75)
Function output:
15
func gcd(_ a: Int, _ b: Int) -> Int {
if b == 0 {
return a
} else {
if a > b {
return gcd(a-b, b)
} else {
return gcd(a, b-a)
}
}
}
8.6 Binary Search
Searching a sorted collection is a common task. For example finding a word in a dictionary, or a number in a phone book.
Binary search is one of the fundamental algorithms in computer science. In its most basic form, binary search finds the position of an element, known as the search key, in a sorted array. It does this by repeatedly halving the search interval. Initially the search interval ranges from the first index of the array to the last index. In each step the algorithm compares the middle value from the search interval with the search key. If the middle value is less than the key, then all the value from the first half of the array are lower than the key, that means that the search key cannot be located in the first half, the search will continue in the second half of the array. The same logic will apply if the middle element is greater than the key. If the middle value is equal to the search key then the key has been found.
Let’s take a few examples to understand the algorithm, left
if the first index of the search interval and right
is the last one:
numbers = [1, 2, 4, 5, 7, 8, 9, 12] // 8 elements
---------------------------------------------------------------------
key = 4
// Step 1 (left = 0, right = 7)
// the middle element is 5 which is greater than 4
// the search will continue in the first half of the search interval
// Step 2 (left = 0, right = 3)
// the middle element is 2 which is less than 4
// the search will continue in the second half of the search interval
// Step 3 (left = 2, right = 3)
// the middle element is 4 - we found the key!
---------------------------------------------------------------------
key = 12
// Step 1 (left = 0, right = 7)
// the middle element is 5 which is less than 12
// the search will continue in the second half of the search interval
// Step 2 (left = 4, right = 7)
// the middle element is 8 which is less than 12
// the search will continue in the second half of the search interval
// Step 3 (left = 6, right = 7)
// the middle element is 9 which is less than 12
// the search will continue in the second half of the search interval
// Step 4 (left = 7, right = 7)
// the search interval has only one element which is equal to the key
---------------------------------------------------------------------
key = 3
// Step 1 (left = 0, right = 7)
// the middle element is 5 which is greater than 3
// the search will continue in the first half of the search interval
// Step 2 (left = 0, right = 3)
// the middle element is 2 which is less than 3
// the search will continue in the second half of the search interval
// Step 3 (left = 2, right = 3)
// the middle element is 4 which is greater than 3
// the search will continue in the first half of the search interval
// Step 4 (left = 2, right = 2)
// the search interval has only one element which is not equal to the key
// the key could not be found in the array
Implement the binary search function using recursion.
func binarySearch(_ key: Int,
_ numbers: [Int],
left: Int = 0,
right: Int = -1) -> Bool
Function call:
binarySearch(2, [1, 2, 4, 5 ,7, 9])
Function output:
true
Function call:
binarySearch(3, [1, 2, 4, 5 ,7, 9])
Function output:
false
Function call:
binarySearch(6, [1, 2, 4, 5 ,7, 9])
Function output:
false
To start off consider the base case, we have to return true when key
is equal to numbers[mid]
.
func binarySearch(_ key: Int,
_ numbers: [Int],
left: Int = 0,
right: Int = -1) -> Bool {
var right = right
if right == -1 {
right = numbers.count - 1
}
if left < right {
var mid = (left + right) / 2
if key < numbers[mid] {
return binarySearch(key, numbers, left: left, right: mid)
} else if key > numbers[mid] {
return binarySearch(key, numbers, left: mid + 1, right: right)
} else {
return true
}
} else {
return numbers[left] == key
}
}
8.7 Towers of Hanoi
There are three pegs labeled A
, B
and C
. On the first peg there are N
stacked disks, each one with a different diameter from biggest (on bottom) to smallest. Move all the disks from the first peg to the second one while respecting the rules:
- only one disk can be moved at a time
- each move consists of taking the upper disk from one of the stacks and placing it on top of another stack
- no disk may be placed on top of a smaller disk
N = 5
* | |
*** | |
***** | |
******* | |
********* | |
---------------------------------
We provide code that will help you visualize the algorithm. When you want to move a disk from a peg to another callmove(from:to:)
:
moveDisk(from: "A", to: "B")
moveDisk(from: "A", to: "C")
moveDisk(from: "B", to: "C")
Output:
* | |
*** | |
***** | |
******* | |
********* | |
---------------------------------
moves from A to B
| | |
*** | |
***** | |
******* | |
********* * |
---------------------------------
moves from A to C
| | |
| | |
***** | |
******* | |
********* * ***
---------------------------------
moves from B to C
| | |
| | |
***** | |
******* | *
********* | ***
---------------------------------
Download this playground to get started.
func hanoi(_ N: Int,
from firstPeg: String = "A",
to secondPeg: String = "B",
using thirdPeg: String = "C") {
// your code here
}
// your code here
Input:
let N = 2
Output:
* | |
*** | |
---------------
moves from A to C
| | |
*** | *
---------------
moves from A to B
| | |
| *** *
---------------
moves from C to B
| * |
| *** |
---------------
Input:
let N = 3
Output:
* | |
*** | |
***** | |
---------------------
moves from A to B
| | |
*** | |
***** * |
---------------------
moves from A to C
| | |
| | |
***** * ***
---------------------
moves from B to C
| | |
| | *
***** | ***
---------------------
moves from A to B
| | |
| | *
| ***** ***
---------------------
moves from C to A
| | |
| | |
* ***** ***
---------------------
moves from C to B
| | |
| *** |
* ***** |
---------------------
moves from A to B
| * |
| *** |
| ***** |
---------------------
To move N disks from a peg A
to peg B
, you must first move N-1
disks from peg A
to peg C
, then move the last disk from A
onto B
and finally move N-1
disks from C
to B
. In other words to solve the Hanoi(N) problem you must first solve the Hanoi(N-1) problem two times. When you only have to move one disk you can just make the move.
func hanoi(_ N: Int,
from firstPeg: String = "A",
to secondPeg: String = "B",
using thirdPeg: String = "C") {
if N == 1 {
moveDisk(from: firstPeg, to: secondPeg)
} else {
hanoi(N - 1, from: firstPeg, to: thirdPeg, using: secondPeg)
moveDisk(from: firstPeg, to: secondPeg)
hanoi(N - 1, from: thirdPeg, to: secondPeg, using: firstPeg)
}
}
hanoi(N)
Swift Programming from Scratch
Read more about the book here.
Feel free to ask any questions in the comments bellow.
Hello Andrei (or is it Pavlos?),
Thanks for the great tutorials and problems. I’m finding recursion difficult, but that’s probably due to the limitations imposed by my brain capacity. For the first time, I’ve had to refer to your solutions, and the problem with solving recursion problems seems to be that there is no general principle that you can refer to. If there was a model, or a sequence of steps, that you could use, that would make it easier to find a solution to recursion problems.
On problem 8.6, I copied your function:
“func binarySearch(key: Int, numbers: [Int], left: Int = 0, right: Int = numbers.count – 1) -> Bool { }” into Xcode playground (v6.2), but it gives an error, which is:
“error: use of unresolved identifier ‘numbers’
func binarySearch(key: Int, numbers: [Int], left: Int = 0, right: Int = numbers.count – 1) -> Bool {”
Am I doing something wrong, or is there a mistake in the code?
Thanks, Peter
It’s Andrei
I changed the binarySearch function. Thanks for noticing that!
Hi Andrei,
Just a couple of things:
1. Should it be “right = numbers.count – 1” instead of “right = numners.count – 1”?
2. Should the “right” parameter have “var” in front of it?
P
Thanks!
Hi Andrei,
For problem 8.3, would you please explain how the two return statements work?
return firstDigits + [lastDigit]
return [number]
Are numbers getting inserted into an undeclared array?
Thanks.
I have the same exact question. I don’t understand the system of returning a Int + array of Ints. Any help explaining this would be most appreciated!
OK, I think I understand now it’s really returning the result of the recursive function (which is an array of Int) + a single element array. They will just be appended together into a single array. Cool.
I like this tutorial, it is very clear and thought out. Makes it easy for people to grasp recursion