Home CPSC 340

Recursion

Overview

We can define the factorial of a number as follows:

$x! = x \cdot (x - 1) \cdot (x -2) ... \cdot 2 \cdot 1$

If we want to write a C++ function that computes the factorial of a number, we can do it with a loop like so:


int fact(int x) {
    int product = 1;
    while(x > 1) {
        product = product * x;
        x--;
    }

    return product;
}

Alternatively we could define the factorial of a number recursively like so:

$x! = x \cdot (x - 1)!$

This means that the factorial of a number x is equal to x times the factorial of x - 1. If we use this definition for 5!, we would have:

$5!= 5 \cdot 4!$

Then replacing 4!, we get:

$5! = 5 \cdot 4 \cdot 3!$

If we keep going, we'll get:

$5! = 5 \cdot 4 \cdot 3 \cdot 2!$

Next, we have:

$5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1!$

If we keep expanding like this, however, we will never be able to stop:

$5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0 \cdot -1 \cdot -2 ...$

Which will give us zero.

When using a recursive definition like this, we will have to specify when to stop. In the factorial definition, we can say that the factorial of 0 is 1, and otherwise it's the recursive definition:

\[ x! = \begin{cases} 1, & \text{when } x = 0 \\ x \cdot (x - 1), & \text{otherwise} \\ \end{cases} \]

Now when we expand a factorial, we will stop at x = 0, and just use the value 1 instead of expanding on forever. Mathematicians frequently use recursive definitions like this.

We can use recursive definitions like this to write code as well. To do this, we just have a function that calls itself. Following is a factorial function based on the recursive definition:


int fact(int x) {
    if(x == 0) {
        return 1;
    } else {
        return x * fact(x - 1);
    }
}

How Recursion Works

If we call fact(4), then we will start to execute the fact function with 4 as a parameter. In doing so, we call fact(3) which then begins to execute. Then fact(2) gets called which calls fact(1) which calls fact(0).

fact(0) stops the recursion by just returning a value of 1 directly. Then the program goes back to where it left off in fact(1) and multiples 1 * 1 and returns 1. Then we are back where we left off in fact(2) which multiplies 2 by the result of fact(1) or 1 giving 2.

fact(2) then returns that 2 up to fact(3) which multiplies 3 by the 2 to get 6. The 6 is then returned up to fact(4) which multiplies 4 by the result of fact(3) or 6 giving 24. Then fact(4) returns to where it was called at with the final answer of 24.

This program demonstrates the recursive factorial.


Infinite Recursion

If the factorial function forgets to check for the 0 value, and always calls itself like so:


int fact(int x) {
    return x * fact(x - 1)
}

Then we run into something called infinite recursion. Infinite recursion is like an infinite loop, except that it will eventually crash the program.

Recall that whenever a function is called, an activation record is pushed onto the stack. The stack is only so big, so if we keep pushing activation records over and over, without popping any, the stack will overfill.

Whenever writing a recursive program, it's important to make sure that there is always a "base case" that returns something directly. The recursive case should then move us closer to the base case so that the recursion will eventually stop. Following are some other examples of recursive functions.


Finding the Sum of an Array

How could we use recursion to find the sum of an array of numbers?


int sum(int* numbers, int size) {
    if (size == 0) {
        return 0;
    }

    int last = numbers[size - 1];
    int rest = sum(numbers, size - 1);
    return last + rest;
}

Palindromes

A palindrome is a word that reads the same backwards as forwards. For example, "step on no pets" or "never odd or even" are palindromes.

How can we write a function to test if a string is a palindrome using the following recursive idea?

"A phrase is a palindrome if the first and last letters are the same, and if the rest of the phrase is also a palindrome."


bool isPalindrome(char* str, int first, int last) {
    if (last <= first)
        return true;

    if (str[first] != str[last])
        return false;

    return isPalindrome(str, first + 1, last - 1);
}

Towers of Hanoi

There is a myth that there is a temple with three large towers. On the first tower are 64 golden rings where each one is smaller than the one under it. Monks at the temple are trying to move all of the rings from the first tower to the third tower.

However they must obey the rule that no ring can be placed on a ring that is smaller than it. To move the rings, they must use the third tower as a place holder to move the rings over while obeying the rule.

The myth states that when the monks are finished, and have moved all 64 rings to the third tower, the world will end.

We want to write a program that will figure out how to move all of the rings over, one by one.

Thinking of this recursively, to move any disc from the left tower to the right tower, we would first have to move all of the discs above it to the middle, then put the disc we want on the right, and then put all of the discs on the middle tower back on top at the right.

This is recursive because in defining how to move a disc, we say that we have to move other discs. This idea can be used to come up with a recursive algorithm like so:


To move a disc from left to right, using middle:
    First move all discs above us to the middle, using right.
    Then move this disc from the left to the right.
    Lastly move all discs from the middle to the right using left.

This program demonstrates this technique to solve the Towers of Hanoi.

This function calls itself twice each time through. This means the total number of steps needed doubles for each additional ring that we add. The number of moves is given in the following table:

RingsSteps
11
23
37
415
531
663
7127
8255
9511
101023
......
6418446744073709551615

The number of steps is defined by the following formula:

$steps(rings) = 2^{rings} - 1$

This means that this algorithm is $O(2^n)$. This is called an exponential algorithm, and is completely impractical for large input sizes.

For doing a small number of discs, this doesn't take too terribly long. On my computer, given how long smaller numbers of discs take, it will take roughly 17 million years for the program to complete if we try all 64. Given that the monks are probably a lot slower than a computer, the world won't be ending any time soon :).


Fibonacci Numbers

The Fibonacci numbers are a sequence of numbers starting with 1 1. Each subsequent number is then the sum of the two previous. We can find Fibonacci numbers with a loop, but we can also use recursion.

A recursive definition of the Fibonacci sequence is as follows:

$fib(1) = 1$

$fib(2) = 1$

$fib(x) = fib(x - 1) + fib(x - 2)$

We can use this definition to get the following function:


int fib(number) {
    if(number < 3) {
        return 1;
    } else {
        return fib(number - 1) + fib(number - 2);
    }
}

This function is also $O(2^n)$. As you can see every call to the function expands into two more, so the number of calls explodes exponentially.

Using a loop to calculate the numbers instead of recursion, we'll have a function like the following:


int fib(int number) {
    int a = 1;
    int b = 1;
    int n = 1;
    for(int i = 2; i < number; i++) {
        n = a + b;
        a = b;
        b = n;
    }

    return n;
}

This Fibonacci function runs far faster. This algorithm is $O(n)$.

There are ways to solve this problem with recursion efficiently (such as this or this), but sometimes the obvious recursive solution is not efficient.


Using Recursion as a Stack

Because function calls cause a push onto the stack, and function returns cause a pop from the stack, we can use recursion to write any algorithm using a stack using recursion. For example, the depth first search algorithm was given as follows:

  1. Set current to the start position.
  2. While current is not the end position:
    1. Mark current as visited.
    2. If we haven't gone left, push left.
    3. If we haven't gone right, push right.
    4. If we haven't gone up, push up.
    5. If we haven't gone down, push down.
    6. If the stack is empty, there is no path!
    7. Set current to pop().
  3. We made it!

We can write this using recursion by replacing the pushes with recursive calls. This program demonstrates a recursive depth first search.


Designing Recursive Functions

Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.