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.
