Recursion
Recursion

• Function calls itself
• Programmer must provide a "stopping mechanism"
• Run-time overhead
• Algorithm sometimes difficult to see
• Used for lots of mathematical formulas that calculate series or f(n) depends on f(n-1)
• Fibonacci
• Factorial
• Summing

To write a recursive function

• Determine recurrence relation
  • Fn (n) = expression relating to Fn (n - 1)
  • Write C++ function named Fn receiving n as a paramter and returning correct type
  • Place code in the function that is the expression relating to Fn (n - 1)
• Determine stopping condition
  • Place the if statement that checks for the stopping condition in the function
  • If the condition is true return the base value
  • Otherwise, make the recursive call. (Expression relating to FN(n - 1)

Recursion vs. Iteration

• Sometimes recursion is more intuitive
• Overhead not needed
• Consider summation

Fibonacci