# Understanding Recursive Functions

Recursion is a programming concept that involves a function or method calling itself continuously until it reaches some stopping condition. It can be looked at as a complementary operation to iteration. Often, we can substitute them with each other, replacing recursion with iteration and iteration with recursion. However, in some instances, recursion yields a cleaner solution when compared to iteration.

First, let’s discuss situations where recursion can work well over an iterative solution. Recursion is typically used in instances where the results of one iteration rely on the results of one or more previous iterations. As an example, consider the formula for calculating a factorial. A factorial is defined as `n! = n*(n-1)*(n-2)*…*1`. When we calculate a factorial, we typically know n, and we need to determine n-1, n-2,…,1 in order to find the solution. Using recursion, the process to compute this is straightforward.

This code has two branches of logic based on what the current value is n is. If the value of n is 0, a 1 is returned. Otherwise, we call the function again using n-1 as the argument, and multiplying the result by n. To understand what this code is doing more clearly, let’s look at a simple example. Suppose we were to call this function for n = 3. When you make a call to a function, your computer will store what made the call, so that it can return to that location with the result of the call. This storage of calls is done using a stack, which is why we typically learn about stacks before recursion. What happens is, on each recursive call, another value is added to the stack, until we reach the stopping condition, which in this case is when n = 0. Once we reach this, the 1 is fed to the previous function call, which can then compute its value, and this continues until we get back to the original function call.

So in the case of n = 3, the first function call is factorial(3). When this starts, it goes to the else condition and calls 3 * factorial(2). The call for factorial(2) also goes to the recursive call, giving us 2 * factorial(1). This continues until we reach n = 0. There are two ways to look at this. One way is by building up a function continually on each function call as follows.

Factorial(3) = 3*factorial(2) = 3*(2*factorial(1)) = 3*(2*(1*factorial(0)))

Once we reach factorial(0), we return 1, and we end up with the following.

3*(2*(1*1))) = 3*2*1 = 6

The second way to look at recursion is by looking at the stack at each recursive call and substituting the value of the top call into the one below it. The build up of the calling stack for the factorial problem