Recursive problem-solving is a powerful technique in computer science. It breaks complex problems into smaller, manageable subproblems, solving them by calling the same function with reduced input. This approach is particularly useful for tasks like factorial calculation, Fibonacci sequence generation, and binary search.

Recursion shines in divide-and-conquer algorithms and data structure traversal. It's used in sorting algorithms like merge sort and quick sort, as well as in tree and graph traversals. Understanding recursive techniques is crucial for efficient problem-solving and algorithm design in computer science.

Recursive Problem-Solving Techniques

Recursive solutions for classic problems

• Factorial
  • Recursive definition multiplies $n$ by the factorial of $n-1$, with base case $0! = 1$
  • Recursive function calls itself with $n-1$ until reaching the base case ($n = 0$)
  • Example: factorial(5) = 5 * factorial(4) = 5 * 4 factorial(3) = ... = 120
• Fibonacci sequence
  • Recursive definition adds the previous two Fibonacci numbers ($F_{n-1} + F_{n-2}$), with base cases $F_0 = 0$ and $F_1 = 1$
  • Recursive function calls itself twice with $n-1$ and $n-2$ until reaching the base cases
  • Example: fib(5) = fib(4) + fib(3) = (fib(3) + fib(2)) + (fib(2) + fib(1)) = ... = 5
• Binary search
  • Recursive approach divides the search space in half and recursively searches the appropriate half based on the target value
  • Base cases occur when the element is found or the search space is exhausted (low > high)
  • Recursive function takes the array, target value, and current search space boundaries (low and high indices)
  • Example: Searching for 42 in [1, 5, 17, 42, 98] recursively searches [42, 98], then [42], finding the target

Divide-and-conquer in recursion

• Divide-and-conquer strategy
  • Breaks down complex problems into smaller, more manageable subproblems
  • Solves the subproblems recursively until reaching base cases
  • Combines the solutions of the subproblems to solve the original problem
• Merge sort example
  • Divides the array into two halves recursively until reaching subarrays of size 1 (base case)
  • Recursively sorts the two halves by calling merge sort on each half
  • Merges the sorted halves by comparing elements from each half and placing them in the correct order
• Quick sort example
  • Chooses a pivot element (often the last element) and partitions the array around it
  • Elements smaller than the pivot are placed before it, while larger elements are placed after it
  • Recursively sorts the subarrays on either side of the pivot until reaching subarrays of size 1 (base case)

Recursion for data structure traversal

• Tree traversal
  • Preorder: Visits the root, then recursively traverses the left subtree, followed by the right subtree
  • Inorder: Recursively traverses the left subtree, visits the root, then recursively traverses the right subtree
  • Postorder: Recursively traverses the left subtree, then the right subtree, and finally visits the root
  • Example: Given a binary tree [1, [2, [4], [5]], [3, [6], [7]]], preorder traversal yields [1, 2, 4, 5, 3, 6, 7]
• Graph traversal
  • Depth-first search (DFS) recursively explores as far as possible along each branch before backtracking
  • Recursive DFS function takes the graph, current node, and a set of visited nodes to avoid revisiting nodes
  • Example: In a graph with nodes A, B, C, and D, DFS starting from A might yield [A, B, D, C]
  • Breadth-first search (BFS) explores all neighboring nodes at the current depth before moving to the next depth level
  • BFS is typically implemented using a queue and iteration, but can be adapted to a recursive approach

Complexity analysis of recursive algorithms

• Time complexity
  • Analyze the number of recursive calls made and the work done in each call
  • Recursive algorithms often have time complexities expressed in terms of the input size $n$
  • Binary search example: $O(\log n)$ time complexity due to halving the search space in each recursive call
• Space complexity
  • Consider the maximum depth of the recursive call stack, which depends on the number of recursive calls
  • Tail recursion optimization can reduce space complexity by avoiding stack overflow
    • Tail recursion occurs when the recursive call is the last operation in the function
    • Compilers can optimize tail recursion to reuse the same stack frame
  • Factorial example: $O(n)$ space complexity due to the recursive call stack depth equaling the input value $n$