Source Code. Projects. Nerd Stuff. Art Stuff.

Lesson 15: Recursion

Recursion

Recursion to Execute a Task

  • Recursion is when a function calls itself.
  • This is actually quite simple, but it can be a mind-bender.
  • Each time a function is called (even if the function is calling itself) a new activation frame is created on the main memory’s stack. So each time a function is called, a new instance of the function is given its own distinct memory space.
  • Recursion is an alternative to iteration (looping). Any loop can be written with recursion instead of iteration.
  • recursivePrint.cpp – Simple recursion example using pointer arithmetic

Recursion to Calculate Values

  • Remember that recursion is when a function calls itself.
  • Recursion can be used to produce output like we saw last time, but it can also be used to calculate a value.
  • Many calculations can be defined recursively, so translate themselves easily to recursive functions. (e.g. factorial or exponents)
  • Any recursive function must have a way of stopping the recursion, so that infinite recursion doesn’t result (just like you have to avoid infinite loops)
  • So the general formula for writing a recursive function is to have a “base case” in which a simple value is returned, and the rest of the cases in which another call to the function will lead us to the value. All cases must eventually reduce to a base case in order to avoid infinite recursion.
  • recursiveFac.cpp – Simple recursion example to calculate factorial