More Recursion (Again, again and again)

This week we did more recursion (YAY!) Specifically, ways to trace recursive functions (easily) and more examples of recursion. One example I found to be quite interesting was the binary search example. The idea of binary search is to divide a sorted list in half, if the number you are looking for is greater than the last number of the first divided list, then you look for the number in the second half. It makes a lot of sense, which is nice to know when some things are quite confusing, especially in comp sci! So how would this work recursively? Doesn't seem too hard, in pseudocode:

• Compare the middle number to the number we are searching for
• if the number we are looking for is the middle number, then we've got it!
• if it is greater, recursively call the function on the list from the middle number (since we know that the middle number is not the number we are searching for, I suppose it is not necessary to include it in the list) to the end of the list
• if it is less, recursively call the function on the list from the beginning to the middle number, but not including the middle number.

 And that's it, we let our handy friend recursion magically take care of the rest! When first learning about recursion, my first thought was to avoid it as best as I can because I wasn't sure if I completely understood it. Surely, there must be another way to implement a function without recursion? In most cases, recursion is much, much, much easier than the same function implemented iteratively. And even if you implement it iteratively, you're bound to make a lot of mistakes! Sometimes, it's not completely obvious what needs to be done, in these cases, it's better to understand what you are trying to do first. Once you know that, start building your code from bottom to top. Understand the base cases, and the rest will magically fall into place!