Chapter 8: Recursion

Swift Programming from Scratch

The Swift Sandbox is integrated, making the exercises interactive. Read more about the book here.

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.

Function Definition

func fibonacci(_ i: Int) -> Int

[collapse]

Example 1

Function call:

fibonacci(3)

Function output:

[collapse]

Example 2

Function call:

fibonacci(4)

Function output:

[collapse]

Example 3

Function call:

fibonacci(5)

Function output:

[collapse]

Example 4

Function call:

fibonacci(6)

Function output:

[collapse]

Hint

Remember that if N > 2 , fibonacci(N) = fibonacci(N - 1) + fibonacci(N - 2)

[collapse]

Solution

func fibonacci(_ i: Int) -> Int {
    if i <= 2 {
        return 1
    } else {
        return fibonacci(i - 1) + fibonacci(i - 2)
    }
}

[collapse]

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.

Function Definition

func factorial(_ N: Int) -> Int

[collapse]

Example 1

Function call:

factorial(3)

Function output:

[collapse]

Example 2

Function call:

factorial(5)

Function output:

[collapse]

Example 3

Function call:

factorial(10)

Function output:

[collapse]

Hint

N! = N * (N - 1)!

[collapse]

Solution

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

[collapse]

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.

This content is restricted to buyers of Online Exercise Platform.

Function Definition

func digits(_ number: Int) -> [Int]

[collapse]

Example 1

Function call:

digits(123)

Function output:

[1, 2, 3]

[collapse]

Example 2

Function call:

digits(0)

Function output:

[0]

[collapse]

Example 3

Function call:

digits(54321)

Function output:

[5, 4, 3, 2, 1]

[collapse]

Hint

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.

[collapse]

Solution

func digits(_ number: Int) -> [Int] {
    if number >= 10 {
        let firstDigits = digits(number / 10)
        let lastDigit = number % 10
        return firstDigits + [lastDigit]
    } else {
        return [number]
    }
}

[collapse]

8.4 Power

Write a recursive function pow that takes two numbers x and y as input and returns x to the power y.

This content is restricted to buyers of Online Exercise Platform.

Function Definition

func pow(_ x: Int, _ y: Int) -> Int

[collapse]

Example 1

Function call:

pow(2, 10)

Function output:

[collapse]

Example 2

Function call:

pow(3, 3)

Function output:

[collapse]

Example 3

Function call:

pow(100, 1)

Function output:

[collapse]

Example 4

Function call:

pow(10, 0)

Function output:

[collapse]

Hint

A simple recursive formula we can use is x^y = x * x ^ (y - 1)

[collapse]

Solution 1: tail recursion

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)
    }
}

[collapse]

Solution 2: Exponentiation by squaring

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
        }
    }
}

[collapse]

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

This content is restricted to buyers of Online Exercise Platform.

Function Definition

func gcd(_ a: Int, _ b: Int) -> Int

[collapse]

Example 1

Function call:

gcd(2, 10)

Function output:

[collapse]

Example 2

Function call:

gcd(9, 6)

Function output:

[collapse]

Example 3

Function call:

gcd(30, 75)

Function output:

[collapse]

Solution

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)
        }
    }
}

[collapse]

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.

This content is restricted to buyers of Online Exercise Platform.

Function Definition

func binarySearch(_ key: Int, 
                  _ numbers: [Int], 
                  left: Int = 0, 
                  right: Int = -1) -> Bool

[collapse]

Example 1

Function call:

binarySearch(2, [1, 2, 4, 5 ,7, 9])

Function output:

true

[collapse]

Example 2

Function call:

binarySearch(3, [1, 2, 4, 5 ,7, 9])

Function output:

false

[collapse]

Example 3

Function call:

binarySearch(6, [1, 2, 4, 5 ,7, 9])

Function output:

false

[collapse]

Hint

To start off consider the base case, we have to return true when key is equal to numbers[mid].

[collapse]

Solution

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
    }
}

[collapse]

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.

Function definition

func hanoi(_ N: Int, 
           from firstPeg: String = "A", 
           to secondPeg: String = "B", 
           using thirdPeg: String = "C") {
    // your code here
}

[collapse]

Code

// your code here

[collapse]

Example 1

Input:

let N = 2

Output:


  *    |    |  
 ***   |    |  
---------------

moves from A to C


  |    |    |  
 ***   |    *  
---------------

moves from A to B


  |    |    |  
  |   ***   *  
---------------

moves from C to B


  |    *    |  
  |   ***   |  
---------------

[collapse]

Example 2

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


   |      *      |   
   |     ***     |   
   |    *****    |   
---------------------

[collapse]

Hint

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.

[collapse]

Solution

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)

[collapse]

Swift Programming from Scratch

8 comments for “Chapter 8: Recursion”

Peter
December 31, 2014 at 1:06 pm
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
- Andrei Puni
  January 2, 2015 at 2:55 pm
  It’s Andrei
  I changed the binarySearch function. Thanks for noticing that!
  - Peter
    January 2, 2015 at 8:53 pm
    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
    - Andrei Puni
      January 2, 2015 at 9:35 pm
      Thanks!
Irwin
February 10, 2015 at 4:38 am
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.
- Michael
  November 26, 2016 at 9:09 pm
  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!
  - Michael
    November 26, 2016 at 9:17 pm
    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.
AlexanderS
September 7, 2015 at 8:38 am
I like this tutorial, it is very clear and thought out. Makes it easy for people to grasp recursion