Introduction to Recursion:

Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller, similar sub-problems. It’s a powerful approach used in various algorithms and data structures.

Fundamentals of Recursive Functions

A recursive function consists of two main components:

1. Base Case: The condition that terminates the recursion.
2. Recursive Case: The part where the function calls itself with modified parameters.

Example: Factorial calculation

#include <iostream>

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

Explanation:

• The factorial function calculates the factorial of a given number n.
• Base case: If n is 0 or 1, the function returns 1 (as 0! and 1! are both defined as 1).
• Recursive case: For any other value of n, the function returns n multiplied by the factorial of n-1.
• The recursion continues until it reaches the base case, effectively computing n * (n-1) * (n-2) * … * 2 * 1.

Types of Recursion

1. Direct Recursion: Function calls itself directly.
2. Indirect Recursion: Function calls another function, which then calls the original function.
3. Linear Recursion: One recursive call per function call.
4. Tree Recursion: Multiple recursive calls per function call.

Example of Tree Recursion (Fibonacci sequence):

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

Explanation:

• This fibonacci function calculates the nth Fibonacci number.
• Base case: If n is 0 or 1, it returns n itself.
• Recursive case: For n > 1, it calls itself twice:
  1. fibonacci(n - 1): Calculates the (n-1)th Fibonacci number
  2. fibonacci(n - 2): Calculates the (n-2)th Fibonacci number
• The results of these two calls are added to get the nth Fibonacci number.
• This is tree recursion because each function call spawns two more recursive calls, creating a tree-like structure of function calls.

Recursion vs Iteration

Common Recursive Algorithms

1. Merge Sort:

   #include <vector>
   
   void merge(std::vector<int>& arr, int l, int m, int r) {
       int n1 = m - l + 1;
       int n2 = r - m;
   
       std::vector<int> L(n1), R(n2);
   
       // Copy data to temporary arrays L[] and R[]
       for (int i = 0; i < n1; i++)
           L[i] = arr[l + i];
       for (int j = 0; j < n2; j++)
           R[j] = arr[m + 1 + j];
   
       // Merge the temporary arrays back into arr[l..r]
       int i = 0, j = 0, k = l;
       while (i < n1 && j < n2) {
           if (L[i] <= R[j]) {
               arr[k] = L[i];
               i++;
           } else {
               arr[k] = R[j];
               j++;
           }
           k++;
       }
   
       // Copy the remaining elements of L[], if any
       while (i < n1) {
           arr[k] = L[i];
           i++;
           k++;
       }
   
       // Copy the remaining elements of R[], if any
       while (j < n2) {
           arr[k] = R[j];
           j++;
           k++;
       }
   }
   
   void mergeSort(std::vector<int>& arr, int l, int r) {
       if (l >= r)
           return;
       int m = l + (r - l) / 2;
       mergeSort(arr, l, m);
       mergeSort(arr, m + 1, r);
       merge(arr, l, m, r);
   }
   

   Explanation:

   • mergeSort function:
     • Base case: If l >= r, the subarray has 0 or 1 element, so it’s already sorted.
     • Recursive case:
       1. Find the middle point m to divide the array into two halves.
       2. Call mergeSort for the first half.
       3. Call mergeSort for the second half.
       4. Merge the two sorted halves.
   • merge function:
     • Creates temporary arrays L[] and R[] to hold the two halves.
     • Copies data to these temporary arrays.
     • Merges the two sorted halves back into the original array.
2. Quick Sort:

   #include <vector>
   
   int partition(std::vector<int>& arr, int low, int high) {
       int pivot = arr[high];  // Choose the last element as pivot
       int i = (low - 1);  // Index of smaller element
   
       for (int j = low; j <= high - 1; j++) {
           // If current element is smaller than the pivot
           if (arr[j] < pivot) {
               i++;  // Increment index of smaller element
               std::swap(arr[i], arr[j]);
           }
       }
       std::swap(arr[i + 1], arr[high]);
       return (i + 1);
   }
   
   void quickSort(std::vector<int>& arr, int low, int high) {
       if (low < high) {
           // pi is partitioning index, arr[pi] is now at right place
           int pi = partition(arr, low, high);
   
           // Separately sort elements before partition and after partition
           quickSort(arr, low, pi - 1);
           quickSort(arr, pi + 1, high);
       }
   }
   

   Explanation:

   • quickSort function:
     • Base case: If low >= high, the subarray has 0 or 1 element, so it’s already sorted.
     • Recursive case:
       1. Partition the array and get the partitioning index.
       2. Recursively sort the left subarray (elements smaller than the pivot).
       3. Recursively sort the right subarray (elements greater than the pivot).
   • partition function:
     • Chooses the last element as the pivot.
     • Places the pivot at its correct position in the sorted array.
     • Places all smaller elements to the left of the pivot and all greater elements to the right.
3. Binary Search:

   int binarySearch(int arr[], int low, int high, int x) {
       if (high >= low) {
           int mid = low + (high - low) / 2;
              
           // If the element is present at the middle itself
           if (arr[mid] == x)
               return mid;
              
           // If element is smaller than mid, then it can only be present in left subarray
           if (arr[mid] > x)
               return binarySearch(arr, low, mid - 1, x);
              
           // Else the element can only be present in right subarray
           return binarySearch(arr, mid + 1, high, x);
       }
          
       // Element is not present in array
       return -1;
   }
   

   Explanation:

   • Base case: If high < low, the element is not in the array, so return -1.
   • Recursive case:
     1. Calculate the middle index mid.
     2. If the element at mid is the target, return mid.
     3. If the target is less than the element at mid, search the left half.
     4. If the target is greater than the element at mid, search the right half.
   • This function assumes the input array is sorted in ascending order.

Optimization Techniques

1. Tail Recursion: A special case where the recursive call is the last operation in the function.

   long long factorialTail(int n, long long accumulator = 1) {
       if (n == 0 || n == 1)
           return accumulator;
       return factorialTail(n - 1, n * accumulator);
   }
   

   Explanation:

   • This is a tail-recursive version of the factorial function.
   • Base case: If n is 0 or 1, return the accumulator.
   • Recursive case: Multiply n with the accumulator and pass it to the next recursive call.
   • The recursive call is the last operation, making it tail-recursive.
   • Many compilers can optimize tail recursion into iteration, potentially saving stack space.
2. Memoization: Storing results of expensive function calls to avoid redundant computations.

   #include <unordered_map>
   
   int fibonacciMemo(int n, std::unordered_map<int, int>& memo) {
       if (memo.find(n) != memo.end())
           return memo[n];
       if (n <= 1)
           return n;
       memo[n] = fibonacciMemo(n-1, memo) + fibonacciMemo(n-2, memo);
       return memo[n];
   }
   
   int fibonacci(int n) {
       std::unordered_map<int, int> memo;
       return fibonacciMemo(n, memo);
   }
   

   Explanation:

   • This implementation uses memoization to optimize the Fibonacci sequence calculation.
   • memo is an unordered_map that stores previously computed Fibonacci numbers.
   • Before computing a Fibonacci number, we check if it’s already in the memo.
   • If it’s not in the memo, we compute it and store the result in the memo.
   • This approach significantly reduces the number of recursive calls for larger values of n.

Practice Problems

Medium Level

1. Tower of Hanoi : https://www.geeksforgeeks.org/problems/tower-of-hanoi-1587115621/1

2. Flood Fill Algorithm : https://www.geeksforgeeks.org/flood-fill-algorithm/

3. Binary to Gray Conversion : https://www.geeksforgeeks.org/program-convert-binary-code-equivalent-gray-code-using-recursion/

4. Length of Longest Pallindromic Substring : https://www.geeksforgeeks.org/length-of-longest-palindromic-sub-string-recursion/?ref=lbp

5. All Possible Paths : https://www.geeksforgeeks.org/print-all-possible-paths-from-top-left-to-bottom-right-of-a-mxn-matrix/

   Hard level

6. Find the Value of a Number raised to its reverse: https://www.geeksforgeeks.org/find-the-value-of-a-number-raised-to-its-reverse/

7. Pallindromic Partition: https://www.geeksforgeeks.org/given-a-string-print-all-possible-palindromic-partition/

8. N Queen Problem: https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/

9. Generate all N digit numbers having absolute difference as K between adjacent digits: https://www.geeksforgeeks.org/generate-all-n-digit-numbers-having-absolute-difference-as-k-between-adjacent-digits/

10. Knight tour Problem: https://www.geeksforgeeks.org/the-knights-tour-problem/

These problems cover various aspects of recursion and will help in developing a deeper understanding of recursive problem-solving techniques in C++.

Top 50 Interview Questions: https://www.geeksforgeeks.org/top-50-interview-problems-on-recursion-algorithm/