The Thing About Recursion

Recursive data structures

Over the past few lectures, we've learned about different types of recursive data structures, mainly trees and linked lists. Trees are essentially linked lists in which each list has two or more sub-lists.

Leap of faith

Something that has been concerning me a bit has been the language used when the online textbook suggests implementing a method which involves recursion. It refers to assuming that the recursive call works is taking a leap of faith. As long as there is a base case for how to actually act on the data when the data is there to be acted upon, there should be no leap of faith involved.

The fear of recursion

That being said, it does always feel like recursion is something strange and unusual which seems to miraculously work. However, the feeling, when carefully examined is due to an unfounded fear. The fear is simply that the function you are calling is not complete. When you type the call into the function, sure, that is the case. But by the time you call the function, it is supposedly finished. The call is simply returning to the beginning of the function and passing a new value. Recursive data structures are very useful and not too hard to wrap your head around. It just takes some getting used to.