**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 to`N`

. 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 call`move(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