Recursion

Recursion was a principle that, upon my initial introduction to it completely blew my mind.  I had no idea whatsoever how to be sure that it was working and while our Professor's assurance to "trust in the base case and write the rest assuming it works" would eventually prove to be exactly what I needed to do I found myself still instinctively tracing every call with my mind just to be certain.

What I didn't understand intuitively was how recursion would help, how it might be any better than iteration (Edit: As of Week 8 this is certainly more apparent, it may help in the future to use this lab earlier so that students become more quickly aware of the benefits of recursion).

The real breakthrough moment for me in understanding how recursion operates was when I was able to break it down in more of a lateral sense.  Rather than looking at repeated self-calls and analyzing their correctness, I was able to see a program that would call itself, and simply subdivide the problem into a number of sub-problems proportional to however many recursions must be evaluated to reach the base case.  Indeed one of the easiest ways I found of understanding it was to compare and contrast with divide-and-conquer algorithms, like merge sort for example, or binary search.  Any programs which run in logn time bear a certain similarity to recursion, at least in the way I tend to conceptualize it, and I wonder if anyone else has also made this connection to facilitate their understanding.