Recursion and Unwinding

Having seemingly finished induction for now, though it will inveitably come up again I'm sure, we've know moved the focus of our lecture towards recursions and time complexity. Recursion was initially a bit of an odd concept to me in programing class. While I didn't have any exceptional difficulty understanding it and it's usefulness, it always seemed much more natural to accomplish the same goal with a series of While loops. However, after enough practice, I began to become more use to the idea of using recursions consistently, if for nothing else because of how it seemed to form a far more elegant solution to most problems. However, after finding closed forms for recursively defined functions in lecture, recursion seems far less elegant. It is somewhat suprising how we define closed forms for recursive functions, as the methods in many ways are rather unintuitive. 

After working on the weeks problem set, and getting stuck at a paticular step, I began to wonder how one would go about proving a closed form could not be found for a function. I would imagine that it's more likely that there are many functions for which we have not yet found the closed form for, rather then we know it is impossible to find a closed form and I for one believe the distinction is important. However, having tried to prove for myself that a function could not have a closed form, and, with Google yielding no useful results, I began to realize a certain failing in my knowledge of proving techniques. For most of the proofs we've done, i've had atleast some idea of the concepts and theorems behind what is necessary to provide insight into what we are proving. Yet, while proving that postage of 5 and 11 cents couldn't make postage of 19 seems black and white, proving that a function couldn't have a closed form is far less intuitive, almost to the point where it feels like i'm trying to prove a cat isn't a dog without knowing what a dog is.