Recursion is a programming technique where a function calls itself directly or indirectly to solve a problem. It's often used to solve problems that can be divided into similar sub-problems.

Time Complexity:

The time complexity of a recursive function depends on the number of times the recursive function is called and the work done per call. For example, the time complexity of the Fibonacci series using recursion is O(2^n).

Space Complexity:

The space complexity of a recursive function is determined by the maximum depth of the recursion stack. Each recursive call adds a new layer to the stack.

How Recursion Works:

Recursion works by breaking down a problem into smaller instances of the same problem. Each recursive call should bring the problem closer to a base case, which is a condition where the recursion stops.

    Step 1: Identify the base case which stops recursion.
    Step 2: Divide the problem into smaller sub-problems.
    Step 3: Call the recursive function with the sub-problems.
    Step 4: Combine the results of the sub-problems.

Example 1: Factorial Calculation

Factorial of a Number:

The factorial of a number n (denoted as n!) is the product of all positive integers less than or equal to n. It can be calculated recursively as n! = n * (n-1)!

    Step 1: Base Case: if n == 0, return 1.
    Step 2: Recursive Case: return n * factorial(n-1).


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

Example 2: Fibonacci Series

Fibonacci Series:

The Fibonacci series is a sequence where each number is the sum of the two preceding ones. It starts from 0 and 1. The nth Fibonacci number can be calculated recursively.

    Step 1: Base Case: if n == 0 return 0, if n == 1 return 1.
    Step 2: Recursive Case: return fibonacci(n-1) + fibonacci(n-2).


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

Example 3: Binary Search

Binary Search:

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item until you've narrowed down the possible locations to just one.

    Step 1: Base Case: if low > high, return -1.
    Step 2: Calculate mid = (low + high) / 2.
    Step 3: If arr[mid] == target, return mid.
    Step 4: If arr[mid] > target, search left half.
    Step 5: Else, search right half.


      int binarySearch(int[] arr, int low, int high, int target) {
          if (low > high) return -1;
          int mid = (low + high) / 2;
          if (arr[mid] == target) return mid;
          if (arr[mid] > target) return binarySearch(arr, low, mid - 1, target);
          return binarySearch(arr, mid + 1, high, target);
      }

Example 4: Tower of Hanoi

Tower of Hanoi:

The Tower of Hanoi is a mathematical puzzle where you have three rods and n disks. The objective is to move the entire stack to another rod, obeying certain rules.

    Step 1: Move n-1 disks from source to auxiliary.
    Step 2: Move nth disk from source to destination.
    Step 3: Move n-1 disks from auxiliary to destination.


      void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
          if (n == 1) {
              System.out.println("Move disk 1 from " + from_rod + " to " + to_rod);
              return;
          }
          towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
          System.out.println("Move disk " + n + " from " + from_rod + " to " + to_rod);
          towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
      }

Example 5: String Reversal

String Reversal:

Reversing a string can be done recursively by reversing the substring that excludes the first character and then appending the first character to the end.

    Step 1: Base Case: if string is empty, return empty string.
    Step 2: Recursive Case: return reverse(substring(1)) + first character.


      String reverse(String s) {
          if (s.isEmpty()) return s;
          return reverse(s.substring(1)) + s.charAt(0);
      }

Example 6: Sum of Digits

Sum of Digits:

The sum of digits of a number can be calculated recursively by adding the last digit to the sum of the remaining digits.

    Step 1: Base Case: if n == 0, return 0.
    Step 2: Recursive Case: return n%10 + sumOfDigits(n/10).


      int sumOfDigits(int n) {
          if (n == 0) return 0;
          return n % 10 + sumOfDigits(n / 10);
      }

Example 7: Power Calculation

Power Calculation:

Calculating the power of a number can be done recursively by multiplying the base by itself for the exponent number of times.

    Step 1: Base Case: if exponent == 0, return 1.
    Step 2: Recursive Case: return base * power(base, exponent-1).


      int power(int base, int exponent) {
          if (exponent == 0) return 1;
          return base * power(base, exponent - 1);
      }

Example 8: Greatest Common Divisor (GCD)

Greatest Common Divisor:

The GCD of two numbers can be found using the Euclidean algorithm, which uses recursion to repeatedly subtract the smaller number from the larger number.

    Step 1: Base Case: if b == 0, return a.
    Step 2: Recursive Case: return gcd(b, a%b).


      int gcd(int a, int b) {
          if (b == 0) return a;
          return gcd(b, a % b);
      }

Example 9: Binary Tree Traversal

Binary Tree Traversal:

Tree traversal is a form of recursion where we visit nodes in a binary tree. There are different types of traversals like inorder, preorder, and postorder.

    Step 1: Inorder: Traverse left subtree, Visit node, Traverse right subtree.
    Step 2: Preorder: Visit node, Traverse left subtree, Traverse right subtree.
    Step 3: Postorder: Traverse left subtree, Traverse right subtree, Visit node.


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

Example 10: Permutations of a String

Permutations of a String:

Generating permutations of a string involves rearranging the characters of the string in all possible orders. This can be achieved using recursion.

    Step 1: Base Case: if string is empty, print permutation.
    Step 2: Recursive Case: Fix a character and permute the remaining string.


      void permute(String str, int l, int r) {
          if (l == r) System.out.println(str);
          else {
              for (int i = l; i <= r; i++) {
                  str = swap(str, l, i);
                  permute(str, l + 1, r);
                  str = swap(str, l, i); // backtrack
              }
          }
      }
      
      String swap(String a, int i, int j) {
          char temp;
          char[] charArray = a.toCharArray();
          temp = charArray[i];
          charArray[i] = charArray[j];
          charArray[j] = temp;
          return String.valueOf(charArray);
      }