Source Code. Projects. Nerd Stuff. Art Stuff.
Lesson 15: 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