Lecture 35

Announcements

CS 4730 (game design) is having a game expo on Friday 18 April from 2:30–4:30 in Rice 120. Play games, be entered in a door prize drawing, and do it all in the name of academia!

Talking Points

Recursion!

Defined in terms of self.

A list of numbers is a number followed by a list of numbers.

A stack of turtles is a turtle on top of a stack of turtles.

Practicing is doing it once and then practicing.

A big tree is a trunk with two smaller trees at its end.

n! = n × (n − 1)!

The following picture is a panda painting two copies of the following picture:

Three parts of Good Recursion

Recursive Case: under some condition it invokes itself.
Base Case: under some condition it does not invoke itself.
Progress: each time it invokes itself it gets closer to the base case.

Missing any one of these three will keep recursion from working.

Examples

What are the three parts in the following?

A branch is a stick with two branches at the end.
A lifetime is a day followed by a lifetime.
n! = n × (n − 1)!
f(n) = f(n − 1) + f(n − 2)
Binary search is finding the correct half of the list and doing binary search in that half.

Example Code

Each of the following methods is missing one piece

// Missing the base case; will try to run forever
public static int factorial1(int n) {
    return n * factorial1(n-1);
}

// Not making progress; will try to run forever
public static int factorial2(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial2(n);
}

// No recursive case; is not a recursive method
public static int factorial3(int n) {
    if (n == 0) {
        return 1;
    }
    return n;
}

The following method has all three parts:

// Correct
public static int factorial3(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

Other Code

We can always turn loops into recursion:

public static int sumOf(int[] list, int i) {
    if (i < list.length) {
        return list[i] + sumOf(list, i+1);
    } else {
        return 0;
    }
}

We can also have code that invokes itself more than once:

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

And it can get pretty complicated...

/**
 * A recursive form of Binary Search; checks only between two given indices
 * @param list          The list of search
 * @param goal          The value we are trying to find in that list
 * @param startingIndex Check from this index...
 * @param endingIndex   ...up to (and including) this index
 * @return The index of the goal, or -1 if the goal is not found
 */
public static int binarySearch(int[] list, int goal, int startingIndex, int endingIndex) {
    if (endingIndex < startingIndex) {
        return -1;
    }
    int middleIndex = (startingIndex + endingIndex) / 2;
    if (list[middleIndex] == goal) {
        return middleIndex;
    } else 	if (list[middleIndex] < goal) {
        return binarySearch(list, goal, startingIndex, middleIndex-1);
    } else {
        return binarySearch(list, goal, middleIndex+1, endingIndex);
    }
}

From Q&A in Lecture

Is there a standard way of diagramming recursion?

You can do memory boxes, but there are so many of them it gets old fast. Two other techniques are common: rewriting and tables.

For rewriting, you keep replacing method invocations with the value they return, like

factorial(6)
6 * factorial(5)
    5 * factorial(4)
        4 * factorial(3)
            3 * factorial(2)
                2 * factorial(1)
                    1
6 * 5 * 4 * 3 * 2 * 1

For a table, you keep track of all the values you know about so far:

n    fib(n)
0    1
1    1
2    fib(1) + fib(0) = 1 + 1 = 2
3    fib(2) + fib(1) = 2 + 1 = 3
4    fib(3) + fib(2) = 3 + 2 = 5
5    fib(4) + fib(3) = 5 + 3 = 8
6    fib(5) + fib(4) = 8 + 5 = 13

Recursion vs. Loops?

Anything one can do the other can do too.

Loops are usually faster than recursion.

Loops work by modifying the values in memory boxes; recursion works by stacking new memory on top of old.

Recursion is much easier to write for things that involve splitting problems into two or more non-trivial pieces, like a tree is a trunk with two smaller trees on the end or to sort a list, sort the first half and sort the second half, then merge the sorted halves.

Recursion with non-ints?

Absolutely! See, e.g., codingbat.com's two sets of recursion problems and Lab 13.

How can I come up with the recursive phrase?

Ask yourself, What's the smallest work I could do and still be contributing to the solution? The answer is the making progress part; the bulk of the work that is left over is the recursive part.

For example, what is the smallest part of sorting a list you can do and still be making progress? (student answered find the smallest element in the list) So then the phrase is to sort a list find the smallest element of the list, put it in front of the list, then sort the rest of the list.