Recently, I've been doing a lot of research in "advance topics" of C++, I am very interested in things like memory management and optimization (I'm currently reading "Introduction to Algorithms" to improve my skills).
In my research, I found the topic of recursion. I studied this topic in my "Data Structures" class in university, but I wanted to understand in a deep way how the computer handles recursion and how it can be used instead loops.
In this post I will be explaining how I understood the role that the stack plays in recursion and how you can apply recursion in linear algebra to obtain the determinant of a matrix.
So... what is the Stack?
The stack is a LIFO data structure (Last in, first out). It is literally what you imagine: when you "push" data, this data will go into the stack and it will sit above the last pushed element converting itself in the new "top" element. This process will repeat each time you "push" data to the stack.
When you want to read an element from the stack, you "pop" the top element of the stack. That is why the last element pushed into the stack is the first element to get out of the stack.
Relation between the Stack and Recursion
Well, when you are running a code (Let's say, a C++ code) the runtime of the language manages the "program-stack" this stack will be the structure used the store the variables used in your code and the calls to the different functions that you invoke in your code.
(Dynamic memory spaces created with the 'new' operator are stored in the "Heap", which is a different structure than the Program-Stack)
Keeping track of the function calls with the Stack makes possible things like passing parameters, returning values and of course: Recursion.
Every time you call a function in your code, the runtime will push a "stack frame" into the stack. The stack frame is a block of information that contains the information of the subrutine. This information includes: the parameters, a return address and the local variables of the function.
When you use recursion, you are pushing a stack frame each time your function calls itself. The Call Stack (or "Program-Stack" as mentioned before) has a finite size per program run (The size is calculated before the program execution), this can lead to a dangerous situation because you can actually surpass the quantity of information that the stack can hold: this is the famous "Stack-Overflow".
But don't hold yourself, the runtime will not be pushing stack frames to the stack all the time. When you use the "Return" argument or when the function terminates its execution, the program will return to the "Return Address" and the stack frame will be pop out of the stack.
This is why is so important to have a base case for the recursion. The base case is the case in which the function will not call itself but return an specific value to the previous call.
The base case assure us that at some point of the recursion the functions will start to "roll back" and this will start to pop the stack frames of the recursion out of the Stack.
If you don't have a base case, you will definitely cause a Stack Overflow.
Using recursion to get the determinant of a Matrix.
So, in the next part I will try to demonstrate how to use recursion to get the determinant of a matrix. (This code is a first draft, so there is room for improvement, feel free to give suggestions about the code).
This code will be using the "Standard Method" for solving determinants, if you don't know how it works, you can find how to do it here.
Now lets see the code:
//We will pass the matrix and the size n of the matrix(nxn)
int determinant(int** matrix, int size){
if(size == 2){
/*This one is the base case!
This case will return the result for the smallest sub-matrix (2x2)*/
return (matrix[0][0] * matrix[1][1]) - (matrix[0][1] * matrix[1][0]);
} else {
//This bool is used for the additions of determinants of the sub-matrices.
//Remember that we will add in a pattern of (+ - + - ...)
bool isNegativeAddition = false;
int determinantResult = 0;
for(int x = 0; x < size; x++){
int i = 0;
//This is a temporary place to store the values for the new matrix
int *numbersForNewRecursiveCall = new int[(size - 1) * (size - 1)];
//We fill the temp with the values of the new sub-matrix
for(int sy = 0; sy < size; sy++){
for(int sx = 0; sx < size; sx++){
if(sy != 0 && sx != x){
numbersForNewRecursiveCall[i] = matrix[sy][sx];
i++;
}
}
}
//Then we fill an Array[][]
i = 0;
int **subMatrix = declareArray(size-1);
for(int sy = 0; sy < size-1; sy++){
for(int sx = 0; sx < size-1; sx++){
subMatrix[sy][sx] = numbersForNewRecursiveCall[i];
i++;
}
}
/*This is the important part:
The if is to determine when we will add or when we will rest
the determinants of the sub-matrix
We will add the value of the previous determinant results with
the multiplication of the value that determines the sub-matrix and
the determinant of that particular sub-matrix*/
if(isNegativeAddition == true){
determinantResult = determinantResult + (matrix[0][x] * determinant(subMatrix, size-1) * -1);
isNegativeAddition = false;
} else {
determinantResult = determinantResult + (matrix[0][x] * determinant(subMatrix, size-1));
isNegativeAddition = true;
}
}
return determinantResult;
}
}
As we can see here, the recursion helps us to go to the smallest matrix possible in the method, get its determinant (base case) and then go up all the way to the addition of the different determinants of the n sub-matrices of the biggest (nxn) matrix.
This is literally my second post trying to give back some knowledge to the community so I will appreciate all the feedback that you guys can give to me. Also, I want to mention that the goal of this was not to code the best method for determinant solving, the goal of this was to explain the Stack and how Recursion works.
Thank you very much for reading this post ~
Oldest comments (0)