In recursion, the base case is a condition that stops the recursive process. It prevents the function from calling itself indefinitely. The base case should be simple and ensure that the recursion will eventually reach it.

      Step 1: Identify the simplest scenario where the problem can be solved directly.
      Step 2: Implement this scenario in your recursive function as a condition.
      Step 3: Ensure that every recursive call progresses towards this base case.


      public int factorial(int n) {
          if (n == 0) return 1; // Base case
          return n * factorial(n - 1); // Recursive case
      }

Various Cases in Recursion

Tail Recursion:

Tail recursion occurs when the recursive call is the last statement in the function. This allows some compilers to optimize the recursion, preventing stack overflow.

      Step 1: Ensure the recursive call is the last operation in the function.
      Step 2: Use an accumulator to carry results through recursive calls.


      public int tailFactorial(int n, int a) {
          if (n == 0) return a;
          return tailFactorial(n - 1, n * a);
      }

Indirect Recursion

Understanding Indirect Recursion:

In indirect recursion, a function calls another function, which eventually calls the first function again. This cycle continues until the base case is met.

      Step 1: Define two functions that call each other.
      Step 2: Ensure each function moves towards a condition that breaks the cycle.


      public void functionA(int n) {
          if (n <= 0) return;
          System.out.println("Function A: " + n);
          functionB(n - 1);
      }

      public void functionB(int n) {
          if (n <= 0) return;
          System.out.println("Function B: " + n);
          functionA(n - 1);
      }

Multiple Recursion

Exploring Multiple Recursion:

Multiple recursion occurs when a function makes more than one recursive call. This is common in algorithms like the Fibonacci sequence.

      Step 1: Identify the problem that requires multiple recursive calls.
      Step 2: Implement the recursive calls ensuring they converge to the base case.


      public int fibonacci(int n) {
          if (n <= 1) return n;
          return fibonacci(n - 1) + fibonacci(n - 2);
      }

Mutual Recursion

Understanding Mutual Recursion:

Mutual recursion involves two or more functions calling each other. It is similar to indirect recursion but involves more than two functions.

      Step 1: Define multiple functions that call each other.
      Step 2: Ensure each function contributes to reaching a base case.


      public boolean isEven(int n) {
          if (n == 0) return true;
          return isOdd(n - 1);
      }

      public boolean isOdd(int n) {
          if (n == 0) return false;
          return isEven(n - 1);
      }

Recursive Backtracking

Exploring Recursive Backtracking:

Recursive backtracking is a technique used in solving constraint satisfaction problems like Sudoku. It involves exploring possible solutions and backtracking when a solution does not work.

      Step 1: Explore possible solutions recursively.
      Step 2: Backtrack when a solution path is invalid.


      public boolean solveSudoku(int[][] board) {
          for (int row = 0; row < 9; row++) {
              for (int col = 0; col < 9; col++) {
                  if (board[row][col] == 0) {
                      for (int num = 1; num <= 9; num++) {
                          if (isSafe(board, row, col, num)) {
                              board[row][col] = num;
                              if (solveSudoku(board)) return true;
                              board[row][col] = 0;
                          }
                      }
                      return false;
                  }
              }
          }
          return true;
      }

Divide and Conquer

Understanding Divide and Conquer:

Divide and conquer is a strategy that involves dividing a problem into smaller subproblems, solving each subproblem recursively, and combining their solutions.

      Step 1: Divide the problem into smaller subproblems.
      Step 2: Solve each subproblem recursively.
      Step 3: Combine the solutions of subproblems to solve the original problem.


      public int mergeSort(int[] array, int left, int right) {
          if (left < right) {
              int mid = (left + right) / 2;
              mergeSort(array, left, mid);
              mergeSort(array, mid + 1, right);
              merge(array, left, mid, right);
          }
      }

Memoization in Recursion

Exploring Memoization:

Memoization is an optimization technique used to speed up recursive algorithms by storing the results of expensive function calls and reusing them when the same inputs occur again.

      Step 1: Create a storage to save results of function calls.
      Step 2: Before making a recursive call, check if the result is already computed.
      Step 3: Use stored results to avoid redundant calculations.


      public int fibonacciMemo(int n, int[] memo) {
          if (n <= 1) return n;
          if (memo[n] != 0) return memo[n];
          memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
          return memo[n];
      }

Recursive Tree Traversals

Understanding Tree Traversals:

Tree traversals are techniques for visiting all the nodes in a tree structure. Recursive approaches are commonly used for traversals like in-order, pre-order, and post-order.

      Step 1: Define the order of visiting nodes (in-order, pre-order, post-order).
      Step 2: Implement the recursive function to visit nodes in the defined order.


      public void inOrderTraversal(TreeNode node) {
          if (node == null) return;
          inOrderTraversal(node.left);
          System.out.print(node.value + " ");
          inOrderTraversal(node.right);
      }