Recursion

Recursion is a programming concept where a function solves a problem by calling itself with smaller instances of the same problem until it reaches a base case.

Algorithm Description

1. Key Components:

   • Base case (termination condition)

   • Recursive case (problem broken down)

   • Progress toward base case

2. Key Requirements:

   • Clear base case to prevent infinite recursion

   • Problem can be broken down into smaller subproblems

   • Each recursive call moves closer to base case

Implementation in Go

Basic Factorial Example

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

Fibonacci Sequence

func fibonacci(n int) int {
    // Base cases
    if n <= 1 {
        return n
    }
    // Recursive case
    return fibonacci(n-1) + fibonacci(n-2)
}

Tree Traversal

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
    var result []int
    
    // Base case
    if root == nil {
        return result
    }
    
    // Recursive case
    result = append(result, inorderTraversal(root.Left)...)
    result = append(result, root.Val)
    result = append(result, inorderTraversal(root.Right)...)
    
    return result
}

Time Complexity: Varies

• Factorial: O(n)

• Fibonacci: O(2ⁿ)

• Tree Traversal: O(n)

Space Complexity: O(n)

• Stack space for recursive calls

• Depth of recursion tree

• Can be optimized with tail recursion

Characteristics

Advantages

1. Clean and elegant code

2. Natural solution for recursive problems

3. Easy to understand and maintain

4. Suitable for tree/graph traversal

Disadvantages

1. Stack overflow for deep recursion

2. Memory overhead

3. May be slower than iterative solutions

4. Not suitable for all problems

Related LeetCode Problems

Easy

1. 509. Fibonacci Number

   • Basic recursion implementation

   • Can be optimized with memoization

   • Time: O(2ⁿ), Space: O(n)

2. 206. Reverse Linked List

   • Recursive linked list manipulation

   • Base case: empty or single node

   • Time: O(n), Space: O(n)

3. 104. Maximum Depth of Binary Tree

   • Tree recursion

   • Bottom-up approach

   • Time: O(n), Space: O(h)

Medium

1. 46. Permutations

   • Backtracking with recursion

   • Generate all possibilities

   • Time: O(n!), Space: O(n)

2. 78. Subsets

   • Power set generation

   • Include/exclude pattern

   • Time: O(2ⁿ), Space: O(n)

3. 394. Decode String

   • String recursion

   • Nested structure handling

   • Time: O(n), Space: O(n)

Hard

1. 37. Sudoku Solver

   • Backtracking recursion

   • Multiple constraints

   • Time: O(9^(nn)), Space: O(nn)

2. 51. N-Queens

   • Classic backtracking

   • Multiple recursive calls

   • Time: O(n!), Space: O(n)

Practice Tips

1. Master the Basics:

   • Identify base case

   • Define recursive case

   • Ensure progress

   • Handle edge cases

2. Common Patterns:

   • Divide and conquer

   • Backtracking

   • Tree traversal

   • String manipulation

3. Optimization Techniques:

   • Tail recursion

   • Memoization

   • Stack elimination

   • Iterative conversion

4. Debug Strategies:

   • Print recursive calls

   • Track stack depth

   • Visualize recursion tree

   • Test with small inputs

Common Variations

1. Recursion Types:

   • Direct recursion

   • Indirect recursion

   • Tail recursion

   • Nested recursion

2. Application Areas:

   • Tree/Graph traversal

   • Divide and conquer

   • Dynamic programming

   • Backtracking

3. Special Cases:

   • Mutual recursion

   • Recursive data structures

   • Multiple base cases

   • Nested recursion

Resources

1. Recursion Visualization

2. Recursion Practice Problems

3. Understanding Recursion