Previous Lecture | Lecture 15 | Next Lecture |

# Lecture 15, Tue 03/03

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