RECURSIVE ALGORITHMS

Recursion is a method of solving problems where a function calls itself to solve a smaller instance of the same problem. The goal is to break down the problem into sufficiently small parts that can be easily solved. Every recursive process consists of two key elements: the base case and the recursive case.
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 Number to immediately demonstrate the essence of recursion, let's consider a simple example—calculating the factorial of a number. The factorial of a number n (denoted as 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
This definition shows how the problem reduces to a smaller version of itself—calculating the factorial of n−1 , until it reaches the base case where n=1, and the result is simply 1.// Java implementation of a recursive factorial function
int factorial(int n) {
if (n == 1) {
return 1; // Base case
    } else {
return n * factorial(n - 1); // Recursive case
    }
}

Base Case Explanation:

In each example, it is crucial to highlight the base case and explain its role in terminating the recursion. The base case is a condition that stops the recursive calls and prevents the function from continuing indefinitely.
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 non-recursive result. The code might look something like this:
if (n == 0) return 1;
Here’s why this base case is important:

Recursion example: Calculating the degree Xn

Xn=X*X*X* … *X= X*Xn-1 * X

Loop solution:

int XN=1;
for(int i=0; i < n; i++)
{
XN=XN*X;
}
printf("XN=%d\n",XN);

Recursion solution

A function should be made that calculates the nth power of the number x as a product of the number x and the power of the number x by the the exponent of power for one less, ie.

Xn = Xn-1 * X

This function as a parameter should receive the basis of degree X, as well as the exponent of degree n. The same function can be called to calculate the n-1 power of the number Ks, which is now passed as the base parameters Ks and as the second parameter exponent, but this time n-1. The procedure is called recursively until the exponent is reduced to the value 1. Within the function "if "the condition test should be set (n == 1) via the command "if" if it is fulfilled in that case the function should return the value 1 because:

X0 = 1

The execution algorithm can be seen in the figure below: Recursive algorithms. Calculating x of the nth exponent
Figure 1: Recursive algorithms. Calculating x of the nth exponent
The function power() is called for the first time in the main function and then the exponent value is n. Within the function, it is checked whether the degree has reached 1, which will happen in the last iteration, which will actually end first. The function then returns value of 1 and this result is used in the penultimate call to determine the value calculated within the function. Then the penultimate returns the value and so on until the initial call is reached within the main methods. Only then do we have a value that is calculated and it can be displayed.
Code that solves this:

C

#include < stdio.h>


int power(int x, int n)
{
if(n==0)
return 1;
else
return x*power(x,n-1) ;
}

int main() {
int XN,X,N;
scanf("%d%d",&X,&N);
XN=power(X,N);//A function call to calculate the power
printf("%d\n" ,XN);
return 0;
}

C++

#include < iostream >

using namespace std;


/* Function to calculate power */
int power(int x, int n)
{
if(n==0)
return 1;
else
return x*power(x,n-1) ;
}

int main() {
int XN,X,N;
cin >> X;
cin >> N;
XN=power(X,N);//Call function to calculate power
cout << XN << endl;
return 0;
}
Examples for exercises using recursion can be found on the page:: Recursive algorithms-examples

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
 Picture

From decimal to binary

​Consider the following problem:Write a recursive function that prints the natural number written in decimal form n in binary form in direct order.
Example 1:
Input
22
Output
​0000 0000 0001 0110
Example 2:
Input
2147483647
Output
​1111 1111 1111 1111​Let's consider how a number in decimal form, for example n=22, is converted into binary form. We need to factor that number using powers of 2 only once. To recall, the powers of the number 2 are:
20=1
21=2
22=4
23=8
24=16
25=32
....
​Number 22 can be obtained:
22=16+4+2=1*24 + 0*23 + 1*22 + 1*21+ 0*20
​So, the coefficients to powers of 2 determine the number:
1 0 1 1 0=16+4+2=1*24 + 0*23 + 1*22 + 1*21+ 0*20
Considering that it is an int data that has 16 bits of memory, so the value at the leftmost position is: 215
​so it is:
22=0+0+ .. +16+4+2=0*215+0*214+...+1*24 + 0*23 + 1*22 + 1*21+ 0*20
​The recursive function should receive the remainder of the number as a parameter, which is initially equal to the entered decimal notation of the number. In each recursion, that number is further transformed by subtracting the first smaller power of 2 from it, if that remainder is smaller or remaining the same otherwise. In each recursion, it is passed as a parameter, also the following mode of the power of the number 2. The initial power is determined by the size of the memory occupied by the data. If it is, for example, a 16-bit integer, then the initial value of the power of the number is 2
215 = 32768 ​Each subsequent one is twice as small. Recursion ends when this number reaches 1.

Converting a Decimal Number to a Binary System

Converting a decimal number to a binary number can be achieved in various ways. One commonly used approach is recursion, where the number is repeatedly divided by 2 until it becomes 0, with the remainder at each division forming the binary result.
Algorithm:
  1. Base Case: If the number is 0, end the recursion.
  2. 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 < stdio.h>
#include < math.h >

/* recursive function that converts from decimal to binary notation.
parameters: n-number in decimal notation, s2- power of number 2 */
void db(int n,int s2)
{
if(n >= s2)
printf("1");
else
printf("0");
if(s2 > 1)
{
int t;
t = (n >= s2)? n-s2 : 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 (n-s2), otherwise t=n */
db(t,s2/2);/* a recursive function call to convert decimal to binary notation */
}
}

int main()
{
int n,s2=1,i=0; /* n-number in decimal notation, s2-power of number 2 */
scanf("%d",&n);
/* the exponent of the power of the number 2 */
while(i < 15){
i++;
s2 *= 2;
}
db(n,s2);/* a recursive function call to convert decimal to binary notation */
return 0;
}

Solution in programming language C++

#include < iostream>

using namespace std;
/* recursive function that converts from decimal to binary notation.
parameters: n-number in decimal notation, s2- power of number 2 */
void db(int n, int s2)
{
if(n >= s2)
cout << "1" << endl;
else
cout << "0" << endl;
if(s2 > 1)
{
int t;
t = (n >= s2)? n-s2 : n;
db(t,s2/2);/* a recursive function call to convert decimal to binary notation */
}
}

int main()
{
int n,s2=1,i=0; /* n-number in decimal notation, s2-power of number 2 */
cin >> n;
/* the exponent of the power of the number 2 */
while(i < 15) {
i++;
s2 *= 2;
}
db(n,s2);/* a recursive function call to convert decimal to binary notation */
return 0;
}

Related: Tower of Hanoi Algorithm

The Tower of Hanoi is a classic recursive algorithm problem where one must move a stack of disks from one peg to another, following rules: move one disk at a time, never place a larger disk on a smaller one, and use an auxiliary peg. It illustrates the power and elegance of recursion.

Explore the full explanation, code, and examples here on SVET PROGRAMIRANJA.

Calculation of the determinant of a square matrix of dimension n

Consider the following task:
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.    The procedure for calculating the determinant can be done by recursion. When developing the determinant D(A) of the matrix A, the matrix is ​​developed according to a certain row or column and is reduced to an expression in which, in addition to the members of the developed row or column, the corresponding cofactors of those elements are needed, which are new determinants extracted from the initial one, if we cross out the row and the column in which the element is located. Therefore, it will be reduced to the determinant of the lower order (see figure 2).
We will define the matrix using a pointer as a two-dimensional dynamic array (int ** A). More about dynamic two-dimensional arrays, how they are defined, loaded, printed, copied, etc. read in the article: Two-dimensional dynamic arrays-matrices.
The code shown below is explained in detail in the mentioned article, and will only be shown here:
#include < stdio.h >
#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)
{
for(int i=0; i < m; i++)
{
for(int j=0; j < n; j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
}
int main()
{
int n;
int **A;
printf("n=?\n");
scanf("%d",&n);
A=(int**)malloc(n*sizeof(int*));
printf("Matrix?\n");
for(int i=0; i < n; i++)
{
A[i]=(int*)malloc(n*sizeof(int));
for(int j=0; j < n; j++)
{
scanf("%d",&A[i][j]);
}
}
printf("The Matrix:\n");
printMatrix(A,n);
return 0;
}
    Now we will create a special function that calculates the determinant, which is called from the main function. We will create a function to which we send as parameters the matrix A, the starting dimension of the matrix n, the row or column by which the matrix is ​​developed r and c, a series of logical variables where the index in the series corresponds to the index of the row, and the value of the element in the series is a logical data, which tells whether the row is crossed out or not(1-yes, 0-no) and is marked as rowP(int*) and finally, the last parameter is the same, but for columns and is marked as colP.
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 < stdio.h >
#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)
{
for(int i=0; i < m; i++)
{
for(int j=0; j < n; j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
}
int main()
{
int n;
int **A;
printf("n=?\n");
scanf("%d",&n);
A=(int**)malloc(n*sizeof(int*));
printf("Matrix?\n");
for(int i=0; i < n; i++)
{
A[i]=(int*)malloc(n*sizeof(int));
for(int j=0; j < n; j++)
{
scanf("%d",&A[i][j]);
}
}
printf("Matrix printing:\n");
printMatrix(A,n);
int * colP=(int*) malloc(n*sizeof(int));
for(int i=0; i < n; i++)
{
colP[i] = 0;
}
int * rowP = (int*) malloc(n*sizeof(int));
for(int i=0; i < n; i++)
{
rowP[i]=0;
}
int r=0,c=-1,continuation=1;
while(continuation)
{
printf("Enter the index of the row and column by which you want to develop the matrix,0 - %d.\n.
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 crossed-out rows, a series of crossed-out columns */
printf("Determinant(A): %d\n",d);
printf("Enter 0 if you want to finish the task!!");
scanf("%d",&continuation);
}
printf("End\n");
return 0;
}
In order to remember the rows crossed out when solving the determinant, and also the columns, two dynamic arrays, rowP and colP, and values ​​initialized to 0, which in C language for logical data(int) means false(false), are introduced.
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.Procedure for determining the determinant of a square matrix - recursive method
Figure 2: Procedure for determining the determinant of a square matrix - recursive method

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 i-row and j-column 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 = n-dim=3-2=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:

The procedure for determining the determinant of a square matrix - recursive method with retention of the original matrix
Figure 3: The procedure for determining the determinant of a square matrix - recursive method with retention of the original matrix
The recursive function determinant() - code is shown below.
/*Determines the determinant of the matrix a
parameters:
a-initial matrix n*n
n-dimension of the square matrix
r-row to develop the matrix or -1 if not developed in order
c-column to develop the matrix or -1 if not developed by column
rowP-niz precrtanih redova u matrici
colP-an array of crossed out rows in a matrix
*/
int determinant(int ** a,int n, int r,int c,int dist, int * rowP, int * colP)
{
int res = 0;
if(dim == 1)
{
int i = 0,j = 0;
while(rowP[i])
{
i++;
}
while(colP[j])
{
j++;
}
res=a[i][j];
}
else
{
int k=1;
if(r != -1 && c == -1) //if the determinant develops in order
{
int disp = n-dim;/*reducing the number of observed rows in the original matrix*/
while(rowP[r]){
r++;
}
r=r%n;/*correction if r > n */
for(int j = 0,t = 0; j < n; j++)
{
if(colP[j])
{
continue;
}
k=(int)pow(-1,(r-pom+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,dim-1,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)
{
int displ = n - dim; /*reducing the number of observed rows in the original matrix */
while(colP[c]){
c++;
}
c = c % n;/*correction if r>n */
for(int i=0,h=0; i < n; i++)
{
if(rowP[i])
{
continue;
}
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,dim-1,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*/
{
printf("Error");
return -1;
}
}
return res;
}
The function receives as a parameter a pointer to a pointer (int ** a), which is actually a pointer to a matrix, and the changes made in the determinant() function will be reflected in the original matrix. Other parameters are the number of rows n, row index r and column c by which the determinant is developed. One of those values ​​must be -1 because the matrix cannot be developed both by row and by column, so if e.g. r=0, and c=-1, it means that the matrix is ​​developed in order with index 0.
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:

Efficiency of Recursion:Recursion is a powerful technique that can simplify the implementation of algorithms, particularly those that involve solving a problem by breaking it down into smaller, similar subproblems. However, it's important to consider both time and space complexity when using recursion.
  • 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 memory-efficient. 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.
Stack Overflow:Recursion relies on the call stack to store information about each function call. If a function recurses too deeply, it can cause a stack overflow, where the call stack exceeds its limit, leading to program failure.
  • 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 depth-first search algorithm into an iterative one using an explicit stack data structure.
def factorial_tail_recursive(n, accumulator=1):
if n == 0:
return accumulator
else:
return factorial_tail_recursive(n - 1, n * accumulator)
  • 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.
Conclusion: While recursion is an elegant and powerful tool, it should be used with caution, especially in scenarios where the depth of recursion could lead to excessive memory usage or stack overflow. Understanding when to use recursion versus iteration, and being aware of optimization techniques like tail recursion, can help in writing more efficient and reliable code.
​​Previous
​|< Binary search		 Next
Recursion - primers>|