Recursion in Computer Science

Recursion

• A method which calls itself or a data-structure defined with references to its own kind.
• Familiar examples:
  • Factorials.
  • The Fibonacci numbers.
  • Fractals.

Warmup: Countdown

public static void countdown(int n) {
    if (n == 0) {
        System.out.println("Bang.");
    } else {
        System.out.println(n + "...");
        countdown(n-1);
    }
}

• Base case: When n is 0, prints "Bang."
• Recursive case: Prints the current value of n and then calls countdown with n-1.

The Factorial Operation

• Define the factorial of a non-negative integer n as:

  • n! = n(n-1)(n-2)…1

• Example:

  • 5! = 54321 = 120

• Calculate the factorial of a non-negative integer n as:

  • fact(n) = \begin{cases} 1 & \text{if } n == 0 \text{ or } n == 1 \ n*fact(n-1) & \text{otherwise} \end{cases}

public static int fact(int n) {
    if (n <= 1)
        return 1;
    else
        return n*fact(n-1);
}

• Base case: If n is less than or equal to 1, return 1.
• Recursive case: Otherwise, return n times the factorial of n-1.

Factorial - A Trace

• fact(5)

• 5 * fact(4)

• 4 * fact(3)

• 3 * fact(2)

• 2 * fact(1)

• 1

• fact(5)

• 5 * fact(4)

• 4 * fact(3)

• 3 * fact(2)

• 2 * 1

• fact(5)

• 5 * fact(4)

• 4 * fact(3)

• 3 * 2

• fact(5)

• 5 * fact(4)

• 4 * 6

• fact(5)

• 5 * 24

• 120

• If the recursion does not progress towards the base case, it leads to a StackOverflowException.

public static int fact(int n) {
    if (n <= 1)
        return 1;
    else
        return n*fact(n);
}

• This code will result in infinite recursion because it doesn't approach the base case.

The Fibonacci Numbers

• Interesting integer sequence found throughout nature.

• Recursively defined:

  • f(n) = \begin{cases} 1 & \text{if } n == 0 \text{ or } n == 1 \ f(n-1)+f(n-2) & \text{otherwise} \end{cases}

• Examples:

  • f(0) = 1
  • f(1) = 1
  • f(2) = 2
  • f(3) = 3
  • f(4) = 5
  • f(5) = 8
  • f(6) = 13
  • f(n) = f(n-1) + f(n-2)

int prev = 1;
int prev2 = 1;
while (true) {
    int tmp = prev + prev2;
    System.out.println(tmp);
    prev2 = prev;
    prev = tmp;
}

• We can also translate the definition into a recursive method:

public static int fib(int n) {
    if (n <= 1)
        return 1;
    else
        return fib(n-1) + fib(n-2);
}

• Implemented in Java becomes:

Fibonacci - A Trace

• f(5)

• f(4) + f(3)

• f(3) + f(2)

• f(1) + f(0)

• f(2) + f(1)

• 1 + 1

• f(5)

• f(4) + f(3)

• f(3) + f(2)

• 2

• f(2) + f(1)

• f(5)

• f(4) + f(3)

• f(3) + f(2)

• 2 + 1

• f(5)

• f(4) + f(3)

• 3

• f(1) + f(0)

• 1 + 1

• f(5)

• f(4) + f(3)

• 3

• 2

• f(5)

• f(4) + f(3)

• 5

• f(5)

• 5 + f(3)

• f(1) + f(0)

• f(2) + f(1)

• 1 + 1

• 1

• f(5)

• 5 + 3

• 8

• Memoization (caching) can be used to optimize the recursive Fibonacci calculation.

• Additional comments:

  • Exponential growth/complexity
  • … branching to asymptotics through 172, then 282

Big-O Complexity Chart

• Horrible: O(n!)
• Bad: O(2^n)
• Fair: O(n^2)
• Good: O(n log n)
• Excellent: O(n), O(log n), O(1)

Efficient Fibonacci

• We can also do it recursively and efficiently:

public static int fib(int steps, int prev2, int prev) {
    if (steps <= 1)
        return prev + prev2;
    else
        return fib(steps - 1, prev, prev + prev2);
}

Fibonacci - A Trace (Efficient)

• f(5, 0, 1)
• f(4, 1, 1)
• f(3, 1, 2)
• f(2, 2, 3)
• f(1, 3, 5)
• 8

Lo Feather Fractal

• Described in Chapter 18 of D&D textbook.

• A geometrical recursion.

• The drawFractal method recursively draws the fractal.

private void drawFractal(int level,
    int xA, int yA, int xB, int yB, Graphics g) {

    if (level == 0) {
        g.drawLine(xA, yA, xB, yB);
    } else {
        // Calculate midpoint between (xA,yA) and (xB,yB)
        int xC = (xA + xB)/2;
        int yC = (yA + yB)/2;

        // Calculate the fourth point (xD, yD) which forms an
        // isosceles right triangle between (xA, yA) and (xC, yC)
        // where the right angle is at (xD, yD)
        int xD = xA + (xC - xA) / 2 - (yC - yA) / 2;
        int yD = yA + (yC - yA) / 2 + (xC - xA) / 2;

        // Recursively draw the fractal.
        drawFractal(level - 1, xD, yD, xA, yA, g);
        drawFractal(level - 1, xD, yD, xC, yC, g);
        drawFractal(level - 1, xD, yD, xB, yB, g);
    }
}

public void paintComponent (Graphics g) {
    super.paintComponent(g);
    drawFractal(level, 40, 40, 350, 350, g);
}