project:week11

**Problem:** How can a problem be solved naturally without loops?

- Recursion happens when a function (directly or indirectly) calls itself
- All recursive functions have two parts
- Base case(s)
- Recursion case(s)

- Short, elegant solutions can be possible with recursion
- Factorial
- Fibonacci
- Anagram

- The stack allows multiple calls of a function to exist at the same time
- Infinite recursion is possible

**Problem:** What are the strengths and weaknesses of recursion?

- Some problems have natural and efficient recursive solutions
- Binary search
- Merge sort

- Binary trees
- Stored in sorted order
- O(log n) search time

- Recursion is generally less efficient than iteration
- Some simple-looking solutions can be very inefficient
- Fibonacci revisited

- In theory, recursion and iteration are functionally equivalent

project/week11.txt · Last modified: 2010/05/11 14:48 by jtk

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported