User Tools

Site Tools


project:week11

Recursion

Lecture 1

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

Examples

Lecture 2

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

Examples

Lab

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