Personal Notes

Recursion is when a function calls itself — either directly or indirectly!

This can be difficult/tricky because...well, when do you stop calling yourself? *eek*

Recursion directly correlates to both mathematical induction and recurrence relations from math. As in those systems, you will need to identify:

• a base case (point of reference, starting/stopping position, etc.)
• a reduction step (reducing the size of the original problem before passing it along to ...yourself)
• a recursive call (calling yourself to finish the job)

The four rules of programming with recursion are:

• know when to stop calling yourself! (the base case)
• make the problem smaller before calling yourself... (the reduction step)
• call yourself...trust that the call to yourself worked. (duh)
• don't waste previous calculations!!! (if at all possible)

Another — albeit similar — view is this one:

       given an initial problem of size n
       unless n is minimal,
          break this into several smaller \__ reduction
             problems of the same nature  /     step
             and apply this approach to   \__ recursive
             each                         /     call
          put the smaller case answers    \
             back together to answer our  |__ build
             size n problem -- include    |   phase
             any size n specific info     /
       else
          just use a canned response for  \__ base
             simple case(s)               /   case(s)