Recursion in DSA

What is Recursion?

In computer science, recursion is a strong programming technique that is used in many algorithms and data structures. In the context of data structures and algorithms, recursion refers to a function calling itself to solve a problem or conduct a computation, either directly or indirectly.

Working & usage of Recursion in DSA:

In data structures, recursion is the process of breaking down a major problem into smaller subproblems that may be solved recursively. This entails creating a function or algorithm that calls a smaller version of the original problem until the problem is small enough to be solved directly. Each recursive call’s output is merged or aggregated to produce the ultimate solution to the original problem.

Components of a recursive function:

A recursive function is made up of two parts:

A base case is a condition that ends the recursion and returns a value without further recursive calls. The base case is usually a simple case that can be solved directly.
A recursive case is the section of the function that calls itself with a smaller version of the original problem and then combines the results of each recursive call to answer the original problem. In the recursive instance, the original problem is frequently broken down into smaller subproblems that can be solved recursively.

Main Recursion Methods in Data Structure Methods:

Various recursion approaches are often used in data structures and algorithms. Here are the five most common recursion methods in DSA:

Linear recursion: Linear recursion is the most basic sort of recursion, in which a function calls itself just once. Each subsequent call moves the problem closer to the base case until the base case is reached and the recursion terminates.
Binary recursion: A type of recursion in which a function calls itself twice is known as binary recursion. Every recursive call divides the problem into two smaller subproblems. This method is frequently used to perform binary search to find a target value in a sorted array.
Multiple recursion: A type of recursion in which a function calls itself several times is known as multiple recursion. Each call divides the problem into smaller subproblems that are then solved recursively.
Mutual recursion: A sort of recursion in which two or more functions call each other in a loop is known as mutual recursion.Each function is dependent on the other to accomplish its purpose, and the recursion continues until the base case is reached.
Indirect recursion: Indirect recursion is a type of recursion in which one or more functions indirectly call themselves.

Examples:

Linear recursion example: Factorial calculation

public static int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1; // base case
    }
    return n * factorial(n - 1); // recursive case
}

Time Complexity: O(n)

Space Complexity: O(n)

Binary recursion example: Binary search algorithm

public static int binarySearch(int[] arr, int target, int low, int high) {
    if (low &gt; high) {
        return -1; // base case - target not found
    }
    int mid = (low + high) / 2;
    if (arr[mid] == target) {
        return mid; // base case - target found
    } else if (arr[mid] &gt; target) {
        return binarySearch(arr, target, low, mid - 1); // recursive case - search left half
    } else {
        return binarySearch(arr, target, mid + 1, high); // recursive case - search right half
    }
}

Time Complexity: O(log n)

Space Complexity: O(log n)

Multiple recursion example: Tower of Hanoi puzzle

public static void towerOfHanoi(int n, char fromRod, char toRod, char auxRod) {
    if (n == 1) {
        System.out.println("Move disk 1 from rod " + fromRod + " to rod " + toRod);
    } else {
        towerOfHanoi(n - 1, fromRod, auxRod, toRod); // move n-1 disks from source to auxiliary rod
        System.out.println("Move disk " + n + " from rod " + fromRod + " to rod " + toRod);
        towerOfHanoi(n - 1, auxRod, toRod, fromRod); // move n-1 disks from auxiliary to destination rod
    }
}

Time Complexity: O(2^n)

Space Complexity: O(n)

Mutual recursion example: Calculation of even and odd numbers

public static void printEven(int n) {
    if (n == 0) {
        return; // base case
    }
    System.out.println(n * 2);
    printOdd(n - 1); // mutual recursion
}

public static void printOdd(int n) {
    if (n == 0) {
        return; // base case
    }
    System.out.println(n * 2 - 1);
    printEven(n - 1); // mutual recursion
}

Time Complexity: O(n)

Space Complexity: O(n)

Indirect recursion example: Fibonacci sequence

public static int fibonacci(int n) {
    if (n == 0 || n == 1) {
        return n; // base case
    }
    return fibonacciHelper(n - 1) + fibonacciHelper(n - 2); // indirect recursion
}

private static int fibonacciHelper(int n) {
    if (n == 0 || n == 1) {
        return n; // base case
    }
    return fibonacci(n - 1) + fibonacci(n - 2); // indirect recursion
}

Time Complexity: O(2^n) [can be optimized to O(n)]

Space Complexity: O(n)

Problems based on recursion:

Given a string S. The task is to print all unique permutations of the given string in lexicographically sorted order.

Example:

Input: ABC
Output:
ABC ACB BAC BCA CAB CBA
Explanation:
Given string ABC has permutations in 6 
forms as ABC, ACB, BAC, BCA, CAB and CBA .

Solution:

import java.util.*;

public class Solution {
    public ArrayList<String> find_permutation(String S) {
        ArrayList<String> result = new ArrayList<>();
        char[] arr = S.toCharArray();
        Arrays.sort(arr);
        String sortedString = new String(arr);
        boolean[] visited = new boolean[S.length()];
        String curr = "";
        permute(sortedString, visited, curr, result);
        return result;
    }
    
    public void permute(String S, boolean[] visited, String curr, ArrayList<String> result) {
        if (curr.length() == S.length()) {
            result.add(curr);
            return;
        }
        for (int i = 0; i < S.length(); i++) {
            if (visited[i] || (i > 0 && S.charAt(i) == S.charAt(i - 1) && !visited[i - 1]))
                continue;
            visited[i] = true;
            curr += S.charAt(i);
            permute(S, visited, curr, result);
            curr = curr.substring(0, curr.length() - 1);
            visited[i] = false;
        }
    }
}

Time Complexity: O(n), where n is length of String

Space Complexity: O(n), where n is length of String

here,

the find_permutation function takes a string S as input and returns an ArrayList of all unique permutations of the string in lexicographically sorted order.
The function first sorts the characters in the input string to ensure that the permutations are generated in sorted order.
It then initializes a boolean array to keep track of the characters that have been visited and a string to store the current permutation being generated.
Finally, it calls the permute function to generate all unique permutations.
The permute function is a recursive function that generates all permutations of the input string.

Given a number and its reverse. Find that number raised to the power of its own reverse.
Note: As answers can be very large, print the result modulo 10⁹ + 7.

Example:

Input:
N = 2
Output: 4
Explanation: The reverse of 2 is 2
and after raising power of 2 by 2 
we get 4 which gives remainder as 
4 by dividing 1000000007.

Solution:

class Solution
{
        
    long power(int N,int R)
    {
          long mod = 1000000007;
    if (R == 0)
        return 1;
    long temp = power(N, R/2);
    temp = (temp * temp) % mod;
    if (R % 2 == 0)
        return temp;
    else
        return (temp * N) % mod;
        
    }

}

Time Complexity: O(log R), where R is the exponent.

Space Complexity: O(log R), where R is the exponent.

In this recursive function, we first check the base case where R is zero, and we simply return 1 as any number raised to the power of 0 is 1.
For all other cases, we recursively calculate the value of N^(R/2) using the power function and store it in a variable temp. We then multiply temp by itself and take modulo mod.
If R is even, we return temp, otherwise, we multiply temp by N and take modulo mod before returning.

Given a string s, remove all its adjacent duplicate characters recursively.

Note: For some test cases, the resultant string would be an empty string. In that case, the function should return the empty string only.

Example:

Input: 
S = "abccbccba"
Output: ""
Explanation: 
ab(cc)b(cc)ba->abbba->a(bbb)a->aa->(aa)->""(empty string)

Solution:

class Solution{
    String rremove(String s) {
        
        if (s.length() < 2) {
        return s; // base case, string length is 0 or 1
    }
    int i = 0;
    while (i < s.length() - 1 && s.charAt(i) == s.charAt(i + 1)) {
        i++; // find index of first non-duplicate character
    }
    if (i > 0) {
        return rremove(s.substring(i + 1)); // remove duplicates and recurse
    } else {
        return s.charAt(0) + rremove(s.substring(1)); // concatenate first character and recurse
    }
    }
}

Time Complexity: O(n)

Space Complexity: O(n)

We start by checking if the length of the string is less than 2, in which case we return the string as it is.
Otherwise, we find the index of the first non-duplicate character by iterating through the string.
If there are adjacent duplicates, we recurse on the remaining substring after the duplicates.
If there are no duplicates, we concatenate the first character with the result of the recursion on the remaining substring.
The base case is when the string length is 0 or 1, in which case we return the string as it is.

Print numbers from 1 to N without the help of loops.

Example:

Input:
N = 10
Output: 1 2 3 4 5 6 7 8 9 10

Solution:

class Solution{
    public static void printNos(int N)
    {
        if(N == 0) return; // base case
        printNos(N-1); // recursive call with N-1
        System.out.print(N + " "); // print N after the recursive call
    }
}

Time Complexity: O(n)

Space Complexity: O(n)

The idea is to recursively call the printNos function with N-1 until the base case is reached, i.e. when N == 0. Then, we print the numbers in reverse order by printing N after the recursive call.

Note: also read about DSA: Collision in Hashing

Follow Me

If you like my post please follow me to read my latest post on programming and technology.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py

Rabecca Fatima

Staying up to the mark is what defines me. Hi all! I’m Rabecca Fatima a keen learner, great enthusiast, ready to take new challenges as stepping stones towards flying colors.