Recursion
Definition of recursion
Using recursion instead of loops
Algorithms using loops (while/for) can be written using recursion
Factorial, palindrome, reversing a sentence, binary search
Some problems only have naturally recursive solutions
Towers of Hanoi, traversing a binary tree, maze
Building a recursive function
base case (could be more than one)
the recursive call (could be more than one)
Recursion analysis
Tracing a recursive function
“Light discussion” of the memory stack
Stack overflow (infinite recursion)
Recursion versus Iteration
Elegance
Performance
Good use of recursion
Towers of Hanoi, Koch snowflake, Sierpinski Triangle, flood fill, and more advanced applications including binary trees and backtracking (8 Queens, solving a maze, Sudoku, …)
Bad use of recursion
Anywhere that iteration can be effectively applied, such as reversing sentences and numbers, power, factorial, gcd, …
READINGS
Chapter 3 pp. 54-56
Turtle Graphics for Tk: http://docs.python.org/library/turtle.html
SUGGESTED EXERCISES FROM THE TEXTBOOK (for students to do)
12, 13, 17, 18, 19