RECURSIVE ALGORITHMS
A given problem that is complex is first divided into several smaller problems, which are easier to solve. Each of these subproblems is solved independently of each other and when each of them is solved, then these solutions are combined and thus solve a complex problem, since when it worked.
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).
Recursion example: Calculating the degree Xn
Xn=X*X*X* … *X= X*Xn-1 * X
Loop solution:
for(int i=0; i < n; i++)
{
printf("XN=%d\n",XN);
Recursion solution
Xn = Xn-1 * X
X0 = 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
21=2
22=4
23=8
24=16
25=32
....
Considering that it is an int data that has 16 bits of memory, so the value at the leftmost position is:
|
215
|
215 = 32768
|
Each subsequent one is twice as small. Recursion ends when this number reaches 1.
|
Solution in C programming language
#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)
{
{
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()
{
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: n-number in decimal notation, s2- power of number 2 */
void db(int n, int s2)
{
{
t = (n >= s2)? n-s2 : 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 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 < 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 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");
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 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:
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)
{
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,(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)
{
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,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*/
{
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.
Next
Recursion - primers >| |