DSA: Recursion

Recursion is a powerful technique in computer science where a function calls itself to solve a problem. It simplifies complex problems by breaking them into smaller, more manageable sub-problems of the same type. Here’s everything you need to know about recursion:
 
 1. Basic Concept
Recursion has two essential components:

• Base case: The condition under which the recursion terminates. Without a base case, recursion will continue infinitely.
• Recursive case: The part of the function that calls itself with modified parameters, bringing the problem closer to the base case.    2. Types of Recursion - Direct recursion: A function calls itself directly.

 

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

- Indirect recursion: A function calls another function, eventually returning to the original function.

    func A() {
        // do something
        B()
    }
 
    func B() {
        // do something
        A()
    }

 3. How it works (Call Stack)
Recursion relies on the call stack. Every time a recursive function is called, a new frame is added to the stack. When the base case is met, the stack unwinds, and the results are computed from the base case back up the chain.
 
 4. Advantages of Recursion

• Simplifies code for problems that can be broken down into similar sub-problems.
• Elegant and easy to write, especially for problems involving structures like trees, graphs, and linked lists.
• Many algorithms (DFS, divide-and-conquer) are inherently recursive.    5. Disadvantages of Recursion
• Stack overflow: Deep recursion can exhaust the stack memory, leading to a crash. - Performance: Recursive solutions can be slower compared to iterative ones due to the overhead of function calls and stack management. - Tail Recursion: In some languages (not Go), tail recursion can be optimized to prevent stack overflow but Go does not have tail recursion optimization.    6. Recursion vs. Iteration Recursion is often more intuitive for problems like tree traversal or backtracking, while iteration can be more efficient in terms of memory usage for problems like loops or linear computations.    7. Common Use Cases of Recursion a. Factorial The classic example of recursion, where the factorial of a number is calculated by reducing the problem by 1.

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

b. Fibonacci Sequence
Another classic recursive example where each Fibonacci number is the sum of the two preceding ones.

 

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

 
c. Tree Traversals
Tree-based algorithms like pre-order, in-order, and post-order traversals use recursion to traverse the tree's nodes.

 

func inorder(node *TreeNode) {
    if node == nil {
        return
    }
    inorder(node.Left)
    fmt.Println(node.Val)
    inorder(node.Right)
}

 
d. Backtracking
Problems like the N-Queens or Rat in a Maze require exploring all possible configurations, which is naturally suited to recursion.

func solveNQueens(board [][]int, col int) bool {
    if col >= len(board) {
        return true
    }
    for i := 0; i < len(board); i++ {
        if isSafe(board, i, col) {
            board[i][col] = 1
            if solveNQueens(board, col+1) {
                return true
            }
            board[i][col] = 0 // backtrack
        }
    }
    return false
}

 e. Divide and Conquer
Algorithms like Merge Sort and Quick Sort use recursion to divide the problem into smaller sub-problems and solve them individually.

func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}

 
 8. Memoization
Recursion can lead to redundant calculations, especially in problems like Fibonacci. Memoization stores previously computed results to avoid recalculating them.

var memo = map[int]int{}
 
func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    if val, ok := memo[n]; ok {
        return val
    }
    memo[n] = fibonacci(n-1) + fibonacci(n-2)
    return memo[n]
}

 9. Dynamic Programming
Dynamic programming (DP) is an extension of recursion, where overlapping sub-problems are solved efficiently using memoization or tabulation. DP problems often rely on a recursive relation.
 
 10. Tail Recursion
Some languages optimize tail recursion to avoid growing the call stack. A tail-recursive function performs its recursive call as the last action in the function. Go, however, does not perform tail call optimization.

func tailFactorial(n, acc int) int {
    if n == 0 {
        return acc
    }
    return tailFactorial(n-1, acc*n) // Tail recursion
}

 
 11. Common Problems Solved with Recursion
- Permutations and Combinations: Generating all permutations or combinations of a set.

• Tower of Hanoi: Moving disks between rods with specific constraints.
• Subset Sum Problem: Finding all subsets of a set that add up to a given sum.
• Sudoku Solver: Solving puzzles where backtracking is required.
• Graph Traversals: Depth-first search (DFS) is inherently recursive.    12. Visualizing Recursion Visualizing recursion as a recursion tree can help in understanding how the problem is being broken down and recombined. Each recursive call is a node in the tree, and the base case acts as the leaf nodes.    13. Recursion Depth Control In some cases, you might want to control the depth of recursion, either to avoid performance issues or to handle very large inputs efficiently by limiting recursion depth.    14. Best Practices
• Always define a base case to avoid infinite recursion.
• Use memoization for optimization when sub-problems overlap.
• Be mindful of the performance and space limitations caused by deep recursion.