Recursion Again and Again and Again!

This week our main focus has been recursion. I've often asked myself the relevance of mathematical proofs and here it is in the form of recursion. Recursion has its basis in a mathematical idea called induction. I'm almost 100% sure that if I hadn't learned about induction, the concept of recursion would've been much harder to grasp. They both go hand in hand in my understanding of each concept. By that I mean recursion helps me to understand induction more, and induction helps me to understand recursion more.

Recursion isn't something that is easily grasped, and like any other concept, it needs to be practiced. Luckily, that's what labs are for! I found the lab this week to be perhaps the easiest we've done so far, which seems odd because recursion seems to be a difficult topic. I wasn't sure if I exactly understood it. I did find the lab to be slightly challenging but not as challenging as I expected. In fact, it was very straight forward.

Recursion is a useful idea but is it possible that it might not be as useful as we'd like it to be? 
One of my concerns regarding recursion is its performance. Do recursive functions have a better performance than the same function that does not use recursion, or is it dependent on the function itself, ie in some functions, the recursive function has a shorter run-time. Greater research (me googling) in to the subject reveals that it is dependent on the language used. It turns out the languages like Java and C have quite a problem with recursive programs in the sense that they do require a lot of time. Although we aren't that concerned with those languages it does seem interesting to know. It turns out that recursion is also quite costly for Python as well. This would make sense because not only are you calling a recursive function once, but you're calling it as many times at is needed, which can be quite a lot! The actual reason why it is so costly is because it requires "the allocation of a new stack frame" as mentioned here. Which raises a few questions of my own like... What is a stack frame? Why does it need to be "allocated?" A stack frame is the section of memory that is used when a program is executed. This reminds me of the stack data type we learned in class... Are these in anyway related? Similar to the stack data type, we can push and pop stacks. Pushing allows us to save the contents of the register to memory and popping allows us to restore the contents of the register from memory. 

So it turns out that recursion can be useful... sometimes.