Week 7: Recursion

Recursion is a programing technique that uses the function being defined within the definition of that function.  It allows a programmer to break a problem into smaller sub problems that are solved in a similar fashion. 

Initially it may seem strange to use a function while defining it.  It is almost like a dictionary using the word within the definition of that word, but dictionary definitions are not like function definitions.  In a recursive function definition there is a smallest case where no recursion occurs.   Every other function call calls the function on the value before the one being called, and the one before that, and so forth, eventually reaching the smallest case.  Without the smallest case, the function would continue to execute until the maximum recursion depth is met, and then a runtime error would occur.

I like recursion because it makes solving problems easier.  You can use recursion if you can solve a smaller instance of a problem and then use that result to solve a larger problem.  I have found that a lot of problems can be solved in this way.  For example, fractals, Fibonacci sequence, Sierpinski triangles, and trees are all problems that can be solved with recursion.

I also like recursion because it is similar mathematical induction, which, as a math student, I am very used to dealing with.  In mathematical induction there is a base case (or smallest case) where what you are trying to prove is true and then you show what you are trying to prove is true for the n + 1th case by assuming it is true for the nth case.  If I get stuck when solving a problem that uses recursion I think about mathematical induction to get myself back to the right train of though.