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.