Recursion(Java)

Recursion:

Recursion is a programming technique where a function calls itself to solve a problem. It involves breaking a problem down into smaller, similar subproblems.

public class RecursionExample {
    public static void main(String[] args) {
        printDecreasing(5);
    }

    public static void printDecreasing(int n) {
        if (n <= 0) {
            return;
        }

        System.out.println(n);
        printDecreasing(n - 1);
    }
}

Explanation: The printDecreasing function prints numbers from n down to 1 in decreasing order using recursion. When n becomes less than or equal to 0, the function stops calling itself.

Stack Overflow:

A stack overflow occurs when the call stack, which keeps track of function calls, becomes too full due to excessive recursion, leading to a crash.

Print Numbers in Increasing Order:

public class IncreasingOrder {
    public static void main(String[] args) {
        printIncreasing(1, 5);
    }

    public static void printIncreasing(int current, int n) {
        if (current > n) {
            return;
        }

        System.out.println(current);
        printIncreasing(current + 1, n);
    }
}

Explanation: The printIncreasing function prints numbers from a starting value up to n in increasing order using recursion. When the current number exceeds n, the recursion stops.

Factorial of n:

public class Factorial {
    public static void main(String[] args) {
        int n = 5;
        System.out.println(factorial(n));
    }

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

        return n * factorial(n - 1);
    }
}

Explanation: The factorial function calculates the factorial of a number n using recursion. The factorial of 0 is defined as 1, and for other values, it's calculated by multiplying n with the factorial of n-1.

Sum of N Natural Numbers:

public class SumOfN {
    public static void main(String[] args) {
        int n = 5;
        System.out.println(sumOfN(n));
    }

    public static int sumOfN(int n) {
        if (n == 1) {
            return 1;
        }

        return n + sumOfN(n - 1);
    }
}

Explanation: The sumOfN function calculates the sum of the first n natural numbers using recursion. When n becomes 1, the recursion stops.

Print Nth Fibonacci Number:

public class Fibonacci {
    public static void main(String[] args) {
        int n = 7;
        System.out.println(fibonacci(n));
    }

    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }

        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Explanation: The fibonacci function calculates the Nth Fibonacci number using recursion. Fibonacci numbers are defined as the sum of the two previous Fibonacci numbers. The base cases are when n is 0 or 1.

Check if Array is Sorted or Not:

public class ArraySorting {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        System.out.println(isSorted(arr, arr.length));
    }

    public static boolean isSorted(int[] arr, int n) {
        if (n <= 1) {
            return true;
        }

        if (arr[n - 1] < arr[n - 2]) {
            return false;
        }

        return isSorted(arr, n - 1);
    }
}

Explanation: The isSorted function checks if an array of integers is sorted in ascending order using recursion. It compares each element with its previous element to determine if the array is sorted.

First Occurrence and Last Occurrence:

public class Occurrence {
    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 4, 7, 8, 4};
        int target = 4;
        System.out.println("First Occurrence: " + firstOccurrence(arr, arr.length, target));
        System.out.println("Last Occurrence: " + lastOccurrence(arr, arr.length, target));
    }

    public static int firstOccurrence(int[] arr, int n, int target) {
        if (n == 0) {
            return -1;
        }

        if (arr[n - 1] == target) {
            return n - 1;
        }

        return firstOccurrence(arr, n - 1, target);
    }

    public static int lastOccurrence(int[] arr, int n, int target) {
        if (n == 0) {
            return -1;
        }

        if (arr[n - 1] == target) {
            return n - 1;
        }

        return lastOccurrence(arr, n - 1, target);
    }
}

Explanation: The firstOccurrence and lastOccurrence functions find the index of the first and last occurrences of a target element in an array using recursion.

Print x to the Power n:

public class Power {
    public static void main(String[] args) {
        int x = 2;
        int n = 5;
        System.out.println(power(x, n));
    }

    public static int power(int x, int n) {
        if (n == 0) {
            return 1;
        }

        return x * power(x, n - 1);
    }
}

Explanation: The power function calculates the value of x raised to the power n using recursion. It repeatedly multiplies x by itself, n times.

Tiling Problem:

public class Tiling {
    public static void main(String[] args) {
        int n = 4;
        System.out.println(waysToTile(n));
    }

    public static int waysToTile(int n) {
        if (n <= 2) {
            return n;
        }

        return waysToTile(n - 1) + waysToTile(n - 2);
    }
}

Explanation: The waysToTile function calculates the number of ways to tile a floor of size n x 2 using tiles of size 1 x 2 and 2 x 1.

Remove Duplicates in a String:

public class RemoveDuplicates {
    public static void main(String[] args) {
        String input = "programming";
        System.out.println(removeDuplicates(input));
    }

    public static String removeDuplicates(String str) {
        if (str.length() <= 1) {
            return str;
        }

        if (str.charAt(0) == str.charAt(1)) {
            return removeDuplicates(str.substring(1));
        }

        return str.charAt(0) + removeDuplicates(str.substring(1));
    }
}

Explanation: The removeDuplicates function removes consecutive duplicate characters from a string using recursion.

Friends Pairing Problem:

public class FriendsPairing {
    public static void main(String[] args) {
        int n = 3;
        System.out.println(countWays(n));
    }

    public static int countWays(int n) {
        if (n <= 2) {
            return n;
        }

        return countWays(n - 1) + (n - 1) * countWays(n - 2);
    }
}

Explanation: The countWays function calculates the number of ways n friends can pair up or remain single. Each friend can either stay single or pair up with any of the remaining friends.

Binary Strings Problem:

public class BinaryStrings {
    public static void main(String[] args) {
        int n = 3;
        System.out.println(countBinaryStrings(n));
    }

    public static int countBinaryStrings(int n) {
        if (n == 1 || n == 2) {
            return n + 1;
        }

        return countBinaryStrings(n - 1) + countBinaryStrings(n - 2);
    }
}

Explanation: The countBinaryStrings function calculates the number of binary strings of length n that do not have consecutive 1s.

Stack Analysis - Binary Strings:

The "Binary Strings" problem is an example of a problem that can be solved using recursion and dynamic programming. The countBinaryStrings function calculates the number of binary strings of length n that do not have consecutive 1s.

The base cases are n = 1 and n = 2, where the number of valid binary strings is n + 1 (0, 1, 10 for n = 1, and 00, 01, 10, 11 for n = 2).

For larger values of n, the number of valid binary strings of length n is the sum of the count for n - 1 (where we can append 0 to any valid string of length n - 1) and the count for n - 2 (where we can append 01 to any valid string of length n - 2).

This approach breaks down the problem into subproblems and uses previously calculated values to build up the solution.

public class BinaryStringsDP {
    public static void main(String[] args) {
        int n = 3;
        System.out.println(countBinaryStrings(n));
    }

    public static int countBinaryStrings(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 2;
        dp[2] = 3;

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

Explanation: In this code, we're using dynamic programming to solve the "Binary Strings" problem more efficiently. We create an array dp to store the count of valid binary strings of length i at index i. We initialize dp[1] and dp[2] based on the base cases, where the lengths are 1 and 2.

Then, we iterate from i = 3 up to n and fill in the dp array using the recurrence relation dp[i] = dp[i - 1] + dp[i - 2]. This is because the count of valid strings of length i is the sum of the count of valid strings of length i - 1 (where we can append a 0) and the count of valid strings of length i - 2 (where we can append 01).

Finally, we return dp[n] as the answer, which represents the number of valid binary strings of length n.

This approach uses a bottom-up dynamic programming strategy to build up the solution iteratively, which is more efficient than the recursive approach for larger values of n.