54: Recursion. Find Your Base.

Recursion is powerful and takes a bit of getting used to. It’s like splitting your thoughts into multiple tasks that are all similar and waiting on the next thought to complete. I know, it sounds complicated. This episode should help you understand this topic that scares and confuses a lot of people. For the factorial example given in the episode, imagine you have a method declared like this: int fact (int value); This method returns an integer and takes an integer. In order to calculate a factorial, it called itself and passes one less than the value it was called with. It keeps doing this until it eventually calls itself with a value of 1. That’s its base case and is a value that it checks for each time. When it sees that it was called with a value of 1, then it returns 1. And each time it returns in the non-base cases, then it takes the return value and multiplies that with the current value and returns that result. So if this method is called with 4 initially, then the process looks like this: Some outside code calls fact(4) Is 4 equal to 1? No. Call fact(3) Is 3 equal to 1? No. Call fact(2) Is 2 equal to 1? No. Call fact(1) Is 1 equal to 1? Yes. Return 1. The fact(2) instance receives the return value of 1, multiplies it with 2 and returns 2. The fact(3) instance receives the return value of 2, multiplies it with 3 and returns 6. The fact(4) instance receives the return value of 6, multiplies it with 4 and returns 24. The outside code receives the value 24 and has its answer. You can also use recursion to process binary trees. In this case, instead of just calling a recursive method straight to a single base case, the method can call into its left child and then into its right child. There are now multiple base cases. Each node in the binary tree without children becomes a base case. Listen to the full episode for more about recursion, or you can also read the full transcript below. Transcript Imagine a new law that creates a government office with a lot of secret documents and a lot of power. How do you make sure that office doesn’t abuse it’s power? The answer is obvious, right? Appoint a new government office to watch over the first office. Now these are smart officials who created this new law and had the foresight to recognize how easy this would be to spiral completely out of control so they designed the law with an end to this madness in sight. You see, they had the brilliant idea to make the second office just a little less secretive and with just a little less power. They thought they were done and about to take a well deserved vacation when one outspoken official asked, “But, who’s going to watch the watcher?” They debated this for a while and being very creative individuals, decided to just appoint a third office to watch the second. The third would be just a little less secretive and with just a little less power. The thought was that by reducing the secret documents and the power, then there would be less incentive for these watchers to commit a crime. So they could be trusted to perform their duties. They were about to call for that vacation, when the outspoken official stood up and said, “I don’t know. I think we need to continue this process until there are no more secret documents involved and no more power at all. Only then can we trust the last office to do its job.” This caused an uproar with comments like, “How would we pay for all these offices,” and “If there’s no power then how can the final office do anything?” They went on like this for quite a while until they realized that they couldn’t continue creating an infinite number of offices of the same power and they couldn’t have just a few offices that watched each other either. Both of these scenarios would lead to infinite coverups and fraud. They had to find a very small and trustworthy source who could be relied on to always do a simple job wit