Recursion Overview

Thinking About Recursion

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.

Rules for Recursive Functions

1. Test for a base case!

Not including the base case could give us infinite recursion, which would send a stack overflow error our way!
When recurring with number parameters, it's often good to check whether the number is equal to zero or one, but this is something that depends on what you're trying to do.
- if (num === 0) { // ...

2. Change at least one argument when recurring

If we never change the arguments we call the function with, we'll end up in an endless cycle of calling the function, and it'll give us an error.
We've got to change the arguments so they get closer to the base case each time, so that eventually they'll hit that base case and we'll stop recurring.
When recurring with number parameters, for example, subtracting one from the number can make it smaller until it will eventually reach a base case of zero or one.

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.