Recursion

In my opinion, recursion hails from the same neighbourhood as OOP. Both are abstractions designed to allow computer code to be designed cleaner and easier for human being to understand. However, recursive code is really just a way of paraphrasing a long series of operations out computer does in it's usual iterative, procedural manner.

Recursive code is code that solves a problem by braking it down into smaller subproblems with identical structure, and repeating the breaking down until it reaches a trivial base case. The code then can return the answer to this base case, and from this answer build up the answer to the original problem. It is a mirror of mathematical induction, the act of taking a problem indexed by the natural numbers, proving it is solve for 1, and then proving that the solution for any number implies the solution to the next. Recursion uses an inductive solution but runs through it backwards.

I have to say, recursion and induction are beautiful concepts in their own right, but their usage should be applied properly in programming. While induction is elegant and quick at proving the validity of an argument, recursion has to use the validity of that argument to compute an value. It is at this point that recursions detriments start to show.

A recursive function calling itself with a smaller case has to create another entry in the call stack of your program. This takes both time and memory. While for smaller cases this isn't necessarily a big detriments, recursive code that had to call a thousand or two thousand copies of itself to solve a case has to deal with the overhead of creating memory for this function call 1000 times. If this is a problem where an iterative solution with a integer used as a counter is possible, one can see how decrementing a counter is much faster and more memory efficient that creating an entry in the call stack.

Therefore, I believe recursion is a very powerful tool to understand a problem, and to write code that makes coincides with our human process of solving the problem. However, the elegance of recursion takes a load off of us and transfers it onto our computers.