Basic concepts of recursion
In computer programming, when a function call itself as a subroutine is known as a recursive function. There are several programming languages that use this process. In the following graphic you can see the basic structure of a recursion function.
Recursion is often seen as an efficient method of programming since it requires the least amount of code to perform the necessary functions. Also, when it is possible, using a recursive function is an efficient way to replace a loop. When someone is creating a recursive function, it is a good practice to add a condition to avoid the recursion to continue indefinitely. In other words, the recursion continues until some condition is met to prevent it.
As we mentioned before, a recursive function always must have a way to stop repeating itself. This kind of function always has two parts: the base case and the recursive case. The base case is when the function stops calling itself. The recursive case is when the function calls itself. This prevents infinite loops.
Some real-world applications of recursion are:
· File trees and parsing
· Game solvers (i.e. Sudoku)
· Fractal designs
· Inductive proofs
· Computer algorithms (List of numbers, Computing the Fibonacci sequence and computing a Factorial)
· Mathematical problems (Towers of Hanoi , Inorder/Preorder/Postorder Tree Traversals, DFS of Graph)
Here is an example of a recursive function. As you can see in the below picture, the function calls itself until the condition n > 0 no longer applies. Once the value of n is equal to zero, the program will no longer run the recursive function. In this example, an initial value of x = 3 is assigned and it will decrease every time the function is used. At the end, when n = 0, the function will print the values obtained previously and the recursion will no longer continue.
After this brief introduction, we are going to explain the following recursive function.
To understand this function, we are going to assign some values to the variables x and y. For this exercise, x = 1.5 and y = 3.0. Also, note in the above function that the value of x is always constant, and the value of y is evaluated and changed every time the function is called as a subroutine. In the next drawing you will see the recursion of this function and how the values change during this process.
If we add a couple of lines to this function, we can see how the value of y changes during the recursion and how the value of x remains constant.
Recursion and Stack
When a function is called, it occupies memory in the stack to store details about the execution of the function. And when the function ends, the memory occupied by it is also released. As we know, recursion is a function that calls itself. Hence at every function call, a block of memory is created in the stack to hold the information of the currently executing function. When the function ends, it returns to it’s calling statement written in the outer function i.e., an outer function is resumed from where it stopped.
Recursive functions use something called “the call stack.” When a program calls a function, that function goes on top of the call stack. This similar to a stack of books. You add things one at a time. Then, when you are ready to take something off, you always take off the top item. In other words, the call stack determinates the rules for the order the function calls will return.
The recursion function previously observed is used to calculate the power of a number, which in this case, is x^y. For purposes of a better understanding of this example, x = 1.5 and y = 3.0 and the result should be 3.375. When the function is called, it goes to the top of the call stack and when it is called again, the second call goes at the top, making the previous call move one position down the stack. This process is repeated until the base case is reached, and the condition needed to stop the recursion is meet, which in this case is y = 1. Due to y = 3, there are going to be three calls and, at the end, the first one will be at the bottom of the stack. Then, once we obtained the condition y = 1, the first call that the program will return will be the one on the top, which in this case is y = 1. After this, the call y = 2 is going to be the call on top and will be the next to return. At the end, y = 3 will be the last call to return.
Here is a drawing in which is explain how the stack organize the function calls of the _pow_recursion and how the same stack returns those calls.
The following graphic shows how the stack organized the calls and delivers the returns during all the recursion process applied to the _pow_recursion function.
Finally, after setting a printf function inside the main function, we can confirm the result of the _pow_recursion function when we set the values x = 1.5 and y = 3.0. As you can see, the result obtained correlates with the result showed on previous graphic.
Sources
(Don´t go out without checking these amazing sources)