RECURSIVE ALGORITHMS
The base case defines the simplest form of the problem that can be solved directly without further function calls. The recursive case defines how the problem is reduced in each step, gradually approaching the base case.
Unlike loops where a particular repeating procedure is specified in the body of the loop, a recursive procedure is also iterative, but a repeating procedure is an algorithm itself that calls itself repeatedly directly or indirectly by a command or function, which then calls a given algorithm (function).
Example: Calculating the Factorial of a NumberTo immediately demonstrate the essence of recursion, let's consider a simple example—calculating the factorial of a number. The factorial of a number nnn (denoted as n!n!n!) is the product of all integers from 1 to nnn. Mathematically, the factorial is defined as:
n!=n×(n−1)×(n−2)×…×1
Using recursion, the factorial can be defined as follows:
n! =  1  if n = 1 
n × (n−1)!  if n > 1 
int factorial(int n) {
if (n == 1) {
return 1; // Base case
} else {
return n * factorial(n  1); // Recursive case
}
}
Base Case Explanation:
For instance, in the case of calculating the power of a number using recursion, the base case is typically when the exponent n equals 0. This is because any number raised to the power of 0 is 1, which is a simple and nonrecursive result. The code might look something like this:
 Stopping Condition: Without a base case, the function would continue to call itself indefinitely, leading to a stack overflow error. The base case provides a stopping point, ensuring that the recursion eventually ends.
 Foundation for the Solution: The base case acts as the foundation on which the entire recursive process is built. Once the base case is reached, the function starts returning values back up the chain of recursive calls, allowing the problem to be solved step by step.
Recursion example: Calculating the degree X^{n}
X^{n}=X*X*X* … *X= X*X^{n1} * X
Loop solution:
for(int i=0; i < n; i++)
{
printf("XN=%d\n",XN);
Recursion solution
X^{n} = X^{n1} * X
X^{0} = 1
Code that solves this:
C
int power(int x, int n)
{
int main() {
scanf("%d%d",&X,&N);
XN=power(X,N);//A function call to calculate the power
printf("%d\n" ,XN);
return 0;
C++
using namespace std;
/* Function to calculate power */
int power(int x, int n)
{
int main() {
cin >> X;
cin >> N;
XN=power(X,N);//Call function to calculate power
cout << XN << endl;
return 0;
Array of Fibonacci
The problem that determines the nth member of the Fibonacci array can be solved, among other things, by recursion: See more about this on webpage:
Array of Fibonacci 
From decimal to binary
Example 1:
Input
22
Output
0000 0000 0001 0110
Example 2:
Input
2147483647
Output
1111 1111 1111 1111
2^{1}=2
2^{2}=4
2^{3}=8
2^{4}=16
2^{5}=32
....
Considering that it is an int data that has 16 bits of memory, so the value at the leftmost position is:

2^{15}

2^{15} = 32768

Each subsequent one is twice as small. Recursion ends when this number reaches 1.

Converting a Decimal Number to a Binary System
Algorithm:
 Base Case: If the number is 0, end the recursion.
 Recursive Case:
 Divide the number by 2 and recursively call the function with the result of that division.
 Print the remainder when dividing the number by 2, which represents the next digit in the binary number.
Solution in C programming language
#include < math.h >
/* recursive function that converts from decimal to binary notation.
parameters: nnumber in decimal notation, s2 power of number 2 */
void db(int n,int s2)
{
{
t = (n >= s2)? ns2 : n; /* If the power of two (s2) is less than the number in the decimal notation, then the remainder (t) is taken as the value of the difference (ns2), otherwise t=n */
db(t,s2/2);/* a recursive function call to convert decimal to binary notation */
int main()
{
scanf("%d",&n);
/* the exponent of the power of the number 2 */
while(i < 15){
s2 *= 2;
db(n,s2);/* a recursive function call to convert decimal to binary notation */
return 0;
Solution in programming language C++
using namespace std;
/* recursive function that converts from decimal to binary notation.
parameters: nnumber in decimal notation, s2 power of number 2 */
void db(int n, int s2)
{
{
t = (n >= s2)? ns2 : n;
db(t,s2/2);/* a recursive function call to convert decimal to binary notation */
int main()
{
cin >> n;
/* the exponent of the power of the number 2 */
while(i < 15) {
s2 *= 2;
db(n,s2);/* a recursive function call to convert decimal to binary notation */
return 0;
Calculation of the determinant of a square matrix of dimension n
Input dimension "n" of matrix A , then enter the matrix. Create an application that solves the determinant of the matrix D(A) and prints it on the screen.
We will define the matrix using a pointer as a twodimensional dynamic array (int ** A). More about dynamic twodimensional arrays, how they are defined, loaded, printed, copied, etc. read in the article: Twodimensional dynamic arraysmatrices.
The code shown below is explained in detail in the mentioned article, and will only be shown here:
#include < stdlib.h >
#include< math.h >
/*Matrix printing function
* parameters are
* a pointer to matrix (pointer to pointer)
* n n matrix dimension
*/
void printMatrix( int ** a, int n)
{
{
{
printf("\n");
int main()
{
int **A;
printf("n=?\n");
scanf("%d",&n);
A=(int**)malloc(n*sizeof(int*));
printf("Matrix?\n");
for(int i=0; i < n; i++)
{
for(int j=0; j < n; j++)
{
printf("The Matrix:\n");
printMatrix(A,n);
return 0;
These parameters need to be prepared in the main function, before calling the function to recursively determine the determinant, and then call the function. The changed main method (function) will now be:
#include < stdlib.h >
#include< math.h >
/* Matrix printing function
* parameters are
* a pointer to matrix (pointer to pointer)
* n matrix dimension
*/
void printMatrix( int ** a, int n)
{
{
{
printf("\n");
int main()
{
int **A;
printf("n=?\n");
scanf("%d",&n);
A=(int**)malloc(n*sizeof(int*));
printf("Matrix?\n");
for(int i=0; i < n; i++)
{
for(int j=0; j < n; j++)
{
printf("Matrix printing:\n");
printMatrix(A,n);
for(int i=0; i < n; i++)
{
int * rowP = (int*) malloc(n*sizeof(int));
for(int i=0; i < n; i++)
{
int r=0,c=1,continuation=1;
while(continuation)
{
Put 1 for the row if the development is by column and vice versa\n",n);
scanf("%d%d",&r,&c);
int d=determinant(A,n,r,c,n,rowP,colP);/* parameters: matrix n*n(A), the order in which it will be developed, column=1 means that it does not develop by column, a series of crossedout rows, a series of crossedout columns */
printf("Determinant(A): %d\n",d);
printf("Enter 0 if you want to finish the task!!");
scanf("%d",&continuation);
printf("End\n");
These pointers will be passed as parameters in the function call to calculate the determinant. The row r and column c along which the determinant is developed are also passed. For example. if it should be developed according to the first row (index i is 0), then r=0, and column c=1. A value of (1) means that it does not evolve per column. If, for example, developed according to the 2nd column (j=1), then it would be r=1, and c=1.
Below is the recursive function determinant()  procedure, and then the code.
Figure 2 shows the procedure for developing a matrix of dimensions 3*3 according to the first order (r=0, c=1), in order to determine the determinant of the same square matrix.
. You can view the procedure for calculating the determinant on the website:Determining the determinant of a square matrix
The algorithm is recursive, ie. to determine the cofactor of a particular member, e.g. cofactor of the element a11=3 (colored in red in the picture), it is necessary to determine the cofactor C11, which represents the lower order determinant, in this example 2*2 and these are the elements [ 6, 3, 1, 7], framed by the red rectangle in the image. Now that cofactor ie. the determinant 2*2 also develops according to the first column, i.e. according to the elements a11=6 and a12=3, and the corresponding cofactors are now the determinants of the first order C11=7 and C12=1 . In addition to the value, the coefficient K= (1)^{i+j} must be taken, where is the irow and jcolumn of the matrix whose determinant is determined (see the table with "+" and "", in the picture. Thus, for the cofactor C12 we get 1 because the coefficient in the first row and first column is K11=(1)^{1+1 }=1. If we were to look at the initial table 3*3 with "+" and "", then we are not looking at the sign of the cofactor in the intersection of the 2nd row and the 2nd column where the matrix element is located  6, but we have to move one place to the left and up, i.e. to dist = ndim=32=1, where n=3 is the initial dimension of the matrix, and dim=2 the current dimension of the matrix, because in the 3*3 matrix the coefficient "" is at the position of the member a22, and actually in the 2*2 matrix it is the position a11, where the sign is "+".
In order to avoid overwriting the cofactor of a matrix element in a new matrix, because this operation, in the case of a large matrix dimension, may require a large number of operations, which would slow down the execution of the program, the determination of the cofactor will be done on the original matrix, by the corresponding row or column is crossed out, which is shown in the following picture, i.e. Figure 3:
parameters:
ainitial matrix n*n
ndimension of the square matrix
rrow to develop the matrix or 1 if not developed in order
ccolumn to develop the matrix or 1 if not developed by column
rowPniz precrtanih redova u matrici
colPan array of crossed out rows in a matrix
*/
int determinant(int ** a,int n, int r,int c,int dist, int * rowP, int * colP)
{
if(dim == 1)
{
while(rowP[i])
{
while(colP[j])
{
res=a[i][j];
else
{
if(r != 1 && c == 1) //if the determinant develops in order
{
while(rowP[r]){
r=r%n;/*correction if r > n */
for(int j = 0,t = 0; j < n; j++)
{
{
k=(int)pow(1,(rpom+t));/*cofactor coefficient (1 or 1)*/
colP[j]=1;/*a crossed out column in a large matrix */
redP[r]=1;/* a crossed out row in a large matrix */
/*A recursive call to the same function*/
int d=determinant(a,n,0,1,dim1,rowP,colP);
printf("red %d, col %d: %d * %d * %d\n",r,j,k,a[r][j],d);
rez=rez+k*a[r][j]*d;
colP[j]=0; /*returned crossed out column in large matrix */
redP[r]=0;/*returned crossed out row in large matrix */
t++;
}
else if(c != 1 && r == 1)
{
while(colP[c]){
c = c % n;/*correction if r>n */
for(int i=0,h=0; i < n; i++)
{
{
k=(int)pow(1,(c  disp + h)); /*cofactor coefficient (1 or 1) */
colP[c]=1;/*a crossed out column in a large matrix
rowP[i]=1;/*a crossed out row in a large matrix */
int d=determinant(a,n,1,0,dim1,rowP,colP);
printf("red %d, col %d: %d * %d * %d\n",i,c,k,a[i][c],d);
res=res + k*a[i][c]*d;
colP[c] = 0;/*returned crossed out column in large matrix */
rowP[i] = 0;/*returned crossed out row in large matrix */
h++;
else /*Error*/
{
return 1;
return res;
The parameter dim is the current dimension of the matrix within the current iteration in the recursion and decreases in each subsequent iteration.
The remaining two parameters rowP and colP are pointers to arrays of type bool(int in C programming language), where the index in the array corresponds to a row, ie. column, and the value, if true(1), indicates that that row or column is crossed out. This is to avoid having to rewrite the corresponding cofactor in a new matrix in each iteration, which would significantly slow down the execution of the program.
Within the function we distinguish two cases, when dim = 1 and dim different from 1. The first is actually the last iteration, when the cofactor is reduced to a matrix of dimension 1 and then the value of the determinant equal to that member of the matrix is returned, where the sign is also taken into account , is it 1 or 1.
In the second part, the matrix is developed, by row r or column c, and the value of the determinant is calculated by creating an expression with members developed, e.g. order and the corresponding cofactor. That cofactor is a new determinant that is obtained from the previous one, by additionally crossing out the row and column in which the mentioned member of the matrix is located. This means that to calculate the cofactor, the same determinant() function must be called again, but now with new prepared parameters as can be seen in the code shown.
Additional Notes:
 Time Complexity: The time complexity of a recursive algorithm depends on how many times the function is called and the operations performed in each call. For example, the time complexity of the recursive algorithm for calculating the Fibonacci sequence is exponential (O(2^n)) due to the overlapping subproblems. In contrast, a recursive binary search has a time complexity of O(log n), which is quite efficient.
 Space Complexity: Recursion can be more demanding on memory compared to iteration. Each recursive call adds a new layer to the call stack, consuming additional space. For algorithms with deep recursion, this can lead to significant memory usage.
 When to Use Iteration: In cases where memory is a concern or when the depth of recursion can become very large, an iterative approach might be more appropriate. Iterative solutions often use constant space (O(1)), making them more memoryefficient. For example, calculating the factorial of a number can be done using both recursion and iteration, but the iterative method is less prone to stack overflow and uses less memory.
 Potential Issues with Deep Recursion: When recursion depth becomes very large (for example, when processing a large dataset or solving a problem with many recursive steps), the risk of a stack overflow increases. This is because each function call adds a frame to the stack, and a deep recursion can exhaust the available stack space.
 Avoiding Stack Overflow:
 Tail Recursion: One way to avoid stack overflow is by using tail recursion, where the recursive call is the last operation in the function. This allows some compilers and interpreters to optimize the recursion by reusing the current function's stack frame for the next call, thus preventing additional stack frames from being added.
 Iterative Conversion: Another approach is to convert the recursive algorithm into an iterative one, which avoids the use of the call stack altogether. For example, converting a recursive depthfirst search algorithm into an iterative one using an explicit stack data structure.
 In this example, the recursive call to factorial_tail_recursive is the last operation in the function, allowing tail call optimization (if supported by the language), which reduces the risk of stack overflow.
Next
Recursion  primers > 