Recursion — How It Works
Recursion! So what is it? It is a mathematical and programming concept or a technique. Generally, all programming languages support this feature, therefore, recursion function.
A function that calls itself. This is actually a powerful technique because it can occur repetition without the help of loops (for or while loops).
Recursion is a very important technique in computer science. There are many problems in computer science; they are solved using recursion algorithm instead of loops. And those problems are naturally recursive in their definition. Let us show you some of them:
The Factorial Function is a classic mathematical function that has a natural recursive definition.
Binary Search is one of the most important computer algorithms. We use this algorithm to find efficiently a desired value inside a data set that might be billions of entries.
The File System of a computer has a recursive definition. Think of its files or directory structures. They can be nested arbitrarily within other directories.
And more…
This is not something that these problems can not be solved without the help of recursion. These can also be done with loops. But there are cases where it is less painful to use recursions instead of loops.
In the following section, we would only consider recursive function instead of loops. We would see how a recursive function works.
The Factorial Function
To demonstrate how recursion works we would use the classical factorial function. This function is naturally recursive. We would see how. The factorial of a positive integer, for example, 4! is the product of integers from 1 to 4.
4! = 4 * 3 * 2 * 1 = 24 The factorial function is mathematically defined as:
If you notice carefully, this is a recursive definition because the factorial recurs on the right side of the equation. For a positive integer n, we can define n! as n * (n - 1)! if the n is greater than or is equal to 1 and here is a special case which is 0!. 0! = 1 if n is equal to 0. Let’s check out how they work:
For n = 1, 1! = n! = n(n – 1)! = 1(1 – 1)! = 1(0)! = 1(1) = 1
For n = 2, 2! = n! = n(n – 1)! = 2(2 – 1)! = 2(1)! = 2(1) = 2
For n = 3, 3! = n! = n(n – 1)! = 3(3 – 1)! = 3(2)! = 3(2) = 6
For n = 4, 4! = n! = n(n – 1)! = 4(4 – 1)! = 4(3)! = 4(6) = 24// and so on
Did you notice to get the product of 4! we used n * (n - 1) four times one by one? This function grows rapidly here. So we should now understand that the factorial of a positive integer has a recursive nature. Because we had to repeat that expression again and again to get the factorial of 4!.
So far, we saw how recursion works using a mathematical way. Now we would look at it using a programming language that supports this feature. Check out the next section.
Rules of Recursion
To work correctly, every recursive function should implement two rules:
- Base case — The base case is what stops the function.
- Recursive case — The recursive case is where the function calls itself.
Keep in mind when you are building a Recursive case, you have to tell the function to go to the Base case at any cost.
Let us create a recursive function. I am using Python. You can use yours. The implementation is as the following:
The base case occurs on line 3 and the recursive case occurs on line 6. In line 6, the function calls itself. This is called function recursion. Calling the same function within the function. The function call happens repeatedly from inside the outermost function. Thus it calls itself until the recursive case falls to the base case.
Now if we want to understand how it works, we need to go through each call of this function. This means how each call to the function works. This process is called Call Stack. Let’s invoke the factorial function we created previously.
factorial(4)Now, we know a recursive function has two cases. As we call the function with an argument of 4 it encounters recursive case instead of the base case. That means the function calls itself there. Check out the further calls to the function on the following diagram:
Here the first call to the factorial function is the outermost function. Besides, this function calls itself 4 more times inside the outermost function by passing 3, 2, 1, and 0 as arguments. Let’s count down. Before the last call we passed 1 as the argument to the function:
return 1 * factorial(0)So, in the last call, the function reaches the base case. Because this time n becomes 0 in the fourth call. The base case is executed when 0 is passed. After that, the recursion is stopped and the chain of returns is started, returning 1, 1, 2, 6, and 24.
Now I hope you understand the function recursion. If not, you should not go through the next section. I would suggest you live with the section above.
The Fibonacci Function
The Fibonacci function is another function that has a recursive definition by nature. This is mathematically defined by:
If you understand how recursive function works, at this point, you may try to generate Fibonacci series: Each number after the second is the sum of the two preceding numbers. For example,
1, 1, 2, 3, 5, 8, 13, ...I hope you would try this one.
Debugging Call Stack
Now, we would watch run after each and every call of the factorial function. I am using PyCharm to debug recursive calls of that function. You may use any IDE you like. So open up the PyCharm.
Here I use the factorial function created in this writing above. On line 2, I set a break-point by clicking on line 2. Then I click Run > Debug menu to start debugging. It then asks which file you want to start with. As I am after factorial.py so I choose this one. Then I check each call clicking on the Step Over option. So try it.
N. B. There is a caution while writing a recursive function. Because if you do not set the base case and recursive case properly then the function will never stop executing itself. Like an infinite loop. So be careful!
That’s it.
