Introduction to Recursion

Recursion is a powerful programming technique in which a function calls itself to solve smaller instances of a problem. Understanding how and when to use recursion can simplify complex problems significantly.

---

What is Recursion?

A recursive function is defined in terms of itself. Every recursive solution must have:

• Base Case – A condition under which the function returns without calling itself.
• Recursive Case – The part where the function calls itself to solve a subproblem.

---

Example: Factorial

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

In this Java example, factorial(5) calls factorial(4), which calls factorial(3), and so on, until it reaches the base case.

---

Stack Behavior

Recursion uses the call stack. Each function call is placed on the stack and waits until deeper calls return.

Poorly written recursive functions may cause stack overflow if the base case is missing or unreachable.

---

When to Use Recursion

Recursion is ideal when:

• The problem can be divided into similar subproblems.
• You’re working with hierarchical data (like trees).
• Iterative solutions are complex or less readable.

---

Common Recursive Problems

• Fibonacci sequence
• Tree traversal (preorder, inorder, postorder)
• Backtracking problems (e.g., Sudoku, N-Queens)
• Divide and conquer algorithms (e.g., MergeSort, QuickSort)

---

Example: Binary Search (Recursive)

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

This recursive binary search breaks the array into smaller pieces at each call.

---

Pros and Cons

Pros:

• Elegant and concise code.
• Great for naturally recursive problems.

Cons:

• Risk of stack overflow.
• Can be less efficient than iteration due to function call overhead.

---

Recursion is a core concept that every developer should master. Once you understand how it works and when it’s appropriate, it becomes a valuable tool in your problem-solving toolkit.