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.
Both problem representations are valuable, the equation format is typically used in algorithm analysis, whereas the stack image is more of an accurate representation of how computer memory handles recursion. Whatever way you choose to look at recursion, you will still get a good picture of how the result is achieved.
From this example, we can get some insight into how recursive functions are constructed. In general, for any recursive function, we need to define the following scenarios.
- The stopping condition: Think of every instance that the algorithm will stop making recursive calls. This typically happens once we reach the end of the problem calculation. This almost always relies on one of the arguments being passed into the function on the recursive calls. Typically, it happens when the argument is either null, or zero, or some other endpoint.
- The recursive call scenario: Think of every instance where you need to make a recursive call in the problem. Sometimes there will be just one, such as the factorial example. Often, however, we may see more than one recursive call in a single function.
If you can define these two components, the actual implementation of the recursive function is easy. We create an if statement, and on the stopping condition, we return a value. On the recursive call condition, we make a recursive call using some modified version of the arguments.
The actual applications are recursive calls can be seen in data structures, looking at trees. Trees heavily rely on recursion to work effectively, so understanding recursion will allow you to implement these structures. Furthermore, recursion sees a lot of use in algorithm design, in techniques such as divide and conquer and dynamic programming.