Recursion: Down the Rabbit Hole and Back
Recursion refers to the order in which code can execute. A recursive program is unique, because it can call itself and repeat the steps from before the recursive call. If the coder is not careful this process can be infinite, but ideally all recursive code has a “base case” that is hit, which causes the program to stop the recursion and begin returning.
Recursion happens on the stack. This means that the results are stored and returned in FIFO (First in First Out) order. So the last recursive call that is made will be the first result returned. This is very important to keep in mind.
If we look at the above code we can trace it with an input and show how the values are stored on the stack.
As we can see in the example, the first call is stored on the bottom of the stack and when the base case of “y == 0” is hit we begin to pop off the values and return the values of the function. We start with returning 1, and then plugging that in to the next call from the top of the stack, and repeat until the stack is empty. As we can see if we plug in x = 4 and y = 3 we end up with the value of 0.015625 being returned.
Recursion is can be a helpful tool for when a repetitive process needs to be done.
If the idea of recursion is till a bit fuzzy it can be also equated to a for loop in C code. The main difference is that the function is calling itself and acts as its own “stop block”.