Lecture 4.
Recursion is a powerful tool for
designing and analyzing algorithms. Today we saw a few recursive mathematical
definitions, as well as a recursive function that in C++ that is a natural
implementation of the recursive definition. A recursive version of binary search
was examine. The complexity analysis for binary search was obtained by solving a
recurrence relation. The "towers of Hanoi" is a puzzle that has a very succinct
recursive solution.
I wrote out a
C++ implementation of the solution and we began to trace out its execution using
a run time stack. On Wednesday I will complete this example and look at other
recursive algorithms.
Posted: Mon - January 15, 2007 at 11:50 AM