When we use recursion, we are calling a function within the body of that same function. When we want to write a recursive function, we need a base case and a recursive case. Our recursive case is where we call our function. In the base case, we do NOT call our function.
When thinking through how to write recursive functions, start small! First think about the simplest possible implementation of the function then work your way up to more complicated cases until you've covered everything.
When we enter the recursive case of a function, we know we're going to be calling the function again. In order to prevent this from happening without end, we need a way to make it so that eventually we'll enter the base case of our function. To do this, we must change the arguments we provide when we call the function in our recursive case.
1. Test for a base case!
2. Change at least one argument when recurring
3. Never make a recursive function call with the same arguments more than once per invocation of a function. If you need to use a recursive result multiple times, store the result in a variable first.