Friday, February 27, 2009

Recursion Part 3

Today we discussed in depth how recursion works. We started with the rules of recursion (base case and make progress toward solution) and then looked at some simple recursive functions that broke these rules. We then looked at how method calls in general work (pushing activation records on the stack) and then reviewed how recursion looks from the point of view of a call stack with multiple activation records. We then looked at call trace for the fibonacci algorithm to show the branching structure of a recursive algorithm that calls itself more than once. We ended the day with the towers of hanoi, and walked through the solution from various angles. We looked at an animated solution - with extremely high tech ui! - and then wrote pseudocode to solve the problem using recursive logic. We walked through the call trace in detail to see how so few lines of code can solve a fairly complex problem in a recursive fashion. Finally we implemented towers of hanoi in class and watched it run successfully.

• You can find the slides for today's lecture here.
• You can find the towers of hanoi source code that we wrote in class, below.

    public static void hanoiRecursive (int disk, int startPeg, int finishPeg, int sparePeg)
    {
    	if (disk < 0)
        {
    	    return;
    	}
    	
        if (disk == 0)
        {
            System.out.println("Move disk " + disk + " from peg " + startPeg +
                    " to peg " + finishPeg);       	
        }
        else
        {
            hanoiRecursive (disk-1, startPeg, sparePeg, finishPeg);
            System.out.println("Move disk " + disk + " from peg " + startPeg +
                " to peg " + finishPeg);
            hanoiRecursive (disk-1, sparePeg, finishPeg, startPeg);
        }
    }


    public void testHanoi ()
    {
    	int numberDisks = 3;
        Recursion.hanoiRecursive(numberDisks, 1, 2, 3);
    }