Recursion

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