RECURSION ALGORITHMS- EXAMPLES

Introduction to recursive algorithms

Recursion is a powerful concept in programming that allows functions to call themselves within their body. This approach is often used to solve problems that can be broken down into smaller, similar subproblems. Recursive algorithms are extremely useful in many areas, including mathematical calculations, searching and sorting data, and for solving complex problems that have natural tree or graph structures.

What is Recursion?

Recursion occurs when a function calls itself to solve a smaller part of the problem. Every recursive function must have a base case that stops further calls, and a recursive case that decomposes the problem into smaller parts. The key to successfully implementing recursion is to design the function in such a way that it handles the base case correctly and handles the recursive cases efficiently.

Advantages of Recursive Algorithms

Practical application

On this page you will find tasks that use recursion to solve various problems. From simple tasks such as calculating the power of a number and adding natural numbers, to more complex challenges such as finding permutations and working with matrices. Each assignment is designed to help you improve your programming skills using recursion.
Before you start solving the problems, we recommend that you study the basic concepts of recursion to better understand the approaches and techniques you will need. Good luck with the solution!
Before you start solving the tasks, read the lesson on the page: Recursive algorithms

1. Degree calculation Xn

Write a program that uses recursion to solve degrees Xn

Input: The real number x (0.8 ≤ x ≤ 1.2) and the integer n (0 ≤ n ≤ 20) are entered from the standard input.Output:

Write a value to the standard output Xn zaokruženu na 5 decimala.

Example:

Input:
1.1
5

Output:

1.61051
Solution: The task is explained in detail on the webpage: Recursion algorithm Recursive Algorithms: y= X ^ n
Figure 1: Recursive Algorithms: y= X ^ n

2. First and second in the rankings

​N participants participated in the athletic competition. At the end of the competition, the results are summarized and a list is formed
 in non-increasing order by the number of getting points , from the highest to the lowest number of points scored. Write a program
which determines the number of points of competitors who are first and second on the ranking list.Input:

The first line of the standard input contains a natural number N (1 ≤ N ≤ 20000) which represents the number competitors. In each of the next N lines there is an integer from the interval [0, 20000], these numbers represent points of competitors, which are not sorted.

Output:

One line of standard output shows the number of points of the first and second competitor on the ranking list.

Example:

Input:
5
70
95
75
30
99

Output:

99
95
Solution

3. Writing numbers inversely and directly

​Write a recursive function that prints numbers from 1 to n in inverse and direct order.​

4. Adding numbers recursively

Create a function that sums the first n natural numbers recursively. In the main method, enter n and call a recursive function to calculate the sum of those numbers.

5. Number of permutations

Enter an integer n, then determine the number of permutations of n elements, using recursion

6. The Fibonacci array

​Enter an integer n and then print the Fibonacci sequence of n elements using recursion. Determine also the sum of all those elements.

7. From decimal to binary form

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

8. The number of squares cut by the diagonal

​A rectangle whose width and height are m[cm] and n[cm] respectively is composed of m*n squares whose sides are 1 cm each. Create a program that, using recursion, determines how many squares will be intersected with the main diagonal of that rectangle.
Example:
Input
5
3
Output
7		 Recursive functions: The number of squares cut by the diagonal of the rectangle that contains them
Figure 1: Recursive functions: The number of squares cut by the diagonal of the rectangle that contains them

Solve the task according to the following algorithm:

  • Enter two integers representing the length and width of rectangles a and b
  • Divide the rectangle into squares of side 1 cm, so that the rectangle looks like a chessboard with b columns and a rows.
  • Determine the coefficient of the diagonal direction as the tangent of the angle (ratio of the width and length of the rectangle b/a)
  • Create a recursive function that returns the number of squares cut by the diagonal of the rectangle
  • Pass the function the initial value of the length of the rectangle, the maximum value of the ymax coordinate in the first column of the square, as well as the direction coefficient.
  • Inside the function, set the passed value for ymax to be ymin now. Determine ymax based on the kednac line ymax = ymin + k*1, where k is the coefficient of the direction transferred as a parameter, and 1 is the length of the side of the square.
  • Inside the function, also, determine the smallest integer value less than the minimum and the smallest integer value greater than the maximum ymax,
    determine the number of squares cut diagonally only in the current column and add it to the total number of squares cut in the following columns.
    This number is obtained by calling the same recursive function again when obtaining the same return value.
  • Do this calculation under the condition that the number of remaining columns is greater than 1
  • In each subsequent call to the recursive function:
    • Reduce the remaining number of columns by 1
    • the maximum value in the current recursion should become the minimum value ymin for the next recursion

/* Solution in programming language C */

#include < stdio.h>
#include < math.h >

int brkv(float n, float ymin, float k)
{
int x;/*the number of intersected squares in the current column*/
int a,b;
float ymax=ymin + k; /*y=k*x*/
a=floor(ymin); /* the first smaller integer */
b=ceil(ymax);/* the first larger integer */
x=b-a;
if(n > 1)
x = x + brkv(n-1, ymax, k); /* What is ymax here will be ymin in the next one */
return x;
} int main()
{
float a,b,k;
scanf("%f%f",&a,&b);
k=b/a; /* coefficient of the direction of the diagonal, i.e., the tangent of the angle that overlaps the diagonal with the side of the rectangle*/
printf("%d",brkv(a,0,k));

return 0;
}

9. Fast scaling algorithm

Write a recursive function to quickly calculate the power of some number: Xn
​Enter an integer n and use the function to calculate the said power.

10. Solitaire

A solitaire of n floors should be whitewashed under the following conditions:
  • each floor is painted either white or blue
  • there must not be 3 white floors one above the other.
In how many ways can one nth floor be painted?

11. Inverse matrix

Enter n and then load a matrix of order n*n. Create a program that calculates the determinant of that matrix and its inverse matrix.
Example: 
Input
3
3 5 6
2 -6 3
0 1 7
Output
-193Solution:
Working with matrices is explained in detail on the website: Two dimensional array-matrix
Calculating the determinant of the matrix is ​​explained in detail on the web page: Recursive Algorithms

The complete solution is explained on the website:

Recursive Algorithms

Optimizing Recursive Algorithms

Recursion is a powerful tool in algorithm design, but it often comes with inefficiencies such as redundant calculations and high memory usage due to deep call stacks. This section focuses on optimizing recursive algorithms through memoization and conversion to iteration, providing practical insights for advanced users.
1. MemoizationMemoization involves storing results of expensive function calls and reusing them when the same inputs occur again. This optimization is particularly useful for problems with overlapping subproblems, such as the Fibonacci sequence or dynamic programming algorithms.

Example: Fibonacci Sequence with Memoization

Java

import java.util.HashMap;

public class Fibonacci {
private static HashMap<Integer, Integer> memo = new HashMap<>();

public static int fibonacci(int n) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);

int result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);
return result;
    }

public static void main(String[] args) {
        System.out.println(fibonacci(10)); // Output: 55
    }
}
In this example, we avoid recalculating the Fibonacci numbers for the same inputs, significantly reducing the time complexity from O(2n) to O(n).
2. Converting Recursion to IterationWhile recursion provides a clean and elegant solution, converting it to an iterative approach can be more efficient by reducing memory usage. For example, consider transforming a recursive solution for factorial into an iterative version:

Recursive Factorial:

public static int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}

Iterative Factorial:

public static int factorialIterative(int n) {
int result = 1;
for (int i = 1; i <= n; i++) {
        result *= i;
    }
return result;
}
​The iterative approach avoids the overhead of recursive calls, making it suitable for systems with limited stack memory.

Advanced Examples

​To challenge learners and deepen their understanding, consider exploring more complex problems:

1. Matrix Determinant Using Recursion

​The determinant of a matrix is an essential concept in linear algebra. A recursive solution breaks down the computation into smaller submatrices:

Java

public static intdeterminant(int[][] matrix) {
if (matrix.length == 1) return matrix[0][0];

int det = 0;
for (int col = 0; col < matrix.length; col++) {
        det += Math.pow(-1, col) * matrix[0][col] * determinant(minor(matrix, 0, col));
    }
return det;
}

private static int[][] minor(int[][] matrix, int row, int col) {
int size = matrix.length - 1;
int[][] minor = new int[size][size];
for (int i = 0, r = 0; i < matrix.length; i++) {
if (i == row) continue;
for (int j = 0, c = 0; j < matrix.length; j++) {
if (j == col) continue;
            minor[r][c++] = matrix[i][j];
        }
        r++;
    }
return minor;
}

2. Tower of Hanoi

​The Tower of Hanoi is a classic recursive problem that involves moving disks between pegs according to specific rules. Here’s the recursive solution:

Java

public static void solveHanoi(int n, char from, char to, char aux) {
if (n == 1) {
        System.out.println("Move disk 1 from " + from + " to " + to);
return;
    }
solveHanoi(n - 1, from, aux, to);
    System.out.println("Move disk " + n + " from " + from + " to " + to);
solveHanoi(n - 1, aux, to, from);
}
​This problem illustrates the essence of recursion with its divide-and-conquer strategy.
Previous
​|< Algorithms examples		 Next
Additional examples with solutions>|