Recursion
Recursion is a concept in both mathematics and computer science in which something is defined by itself, or depends upon itself to function. This may seem confusing at first and it may raise a few questions such as: Why would we do this? How does it work? In this post I hope to explain recursion in detail and answer all of these questions.
In order to understand how recursion works, we should look at an example of it being used. Observe the following code:
Both of these functions do the same thing: calculate the factorial of the number passed into the function. The first function works recursively, while the second uses traditional loops. Calling the function within itself effectively creates a loop back to the top. As you can see, the recursive version is much shorter. This highlights one of the advantages of recursion, and that advantage is efficiency. We can accomplish the same task in many fewer lines than would be required with standard loops.
Recursion also uses an interesting concept called ‘Stacks’ to manage memory while performing calculations. Every time the function is called again within a recursive function, the data from the previous function call is pushed onto a stack. Stacks are just sequential blocks of memory where data is stored in a particular order. This process can be seen in the diagram below.
Now that we understand what recursion is and how it works, the natural question is: Why? Why would we use this as opposed to and iterative solution with loops? We have already mentioned efficiency but that is only part of the story. Recursive functions may also have a reduced time complexity compared to iterative functions. Take some common sorting algorithms for example. One of the fastest and most used algorithms is a recursive function called Quicksort. It is very popular because it has a very fast time complexity compared to some other common algorithms such as Bubble Sort. Recursive functions are also nice because they can be very easy to read since they have so few lines (as seen in the above example). These are a few of the reasons why recursion is so great, and why it would be used as opposed to an iterative solution.
