Previous Lecture

Lecture 15

Next Lecture

Lecture 15, Tue 11/19

Recursion

Topics

• Thinking recursively about problems on sequences
• Recursion vs. iteration via examples: printing elements of an array in order and in reverse order, printing elements of a linked-list in order and in reverse order
• How do we know our recursive solution is correct? Proof by induction
• Is recursive better than iterative?
• Problems that have a naturally recursive solution
• Under the hood of recursive functions (how recursive functions use the stack)
• Helper functions
• Recursion on strings