Module 3: Introduction to Recursion

Master the fundamentals of recursion. Learn how to implement and analyze recursive algorithms.

Module Objectives

Upon completion of this module, you will be able to:

Identify a recursive problem and determine when recursion is appropriate
Define a recursive solution by breaking down a problem into smaller, similar problems
Understand base cases and recursive cases in recursive functions
Trace recursive function calls to understand execution flow
Apply recursive solutions to linked list and tree problems
Analyze the time and space complexity of recursive algorithms

Recursion Basics

What is Recursion?

Recursion is a programming technique where a function calls itself to solve a problem. It's particularly useful for problems that can be broken down into smaller instances of the same problem.

Key Components of Recursion:

Base Case: A condition that stops the recursion
Recursive Case: The function calling itself with a smaller/simpler input
Progress Toward Base Case: Ensuring the recursion will eventually terminate

Simple Example: Factorial

        # Recursive factorial function
        def factorial(n):
        # Base case
        if n == 0 or n == 1:
        return 1
        # Recursive case
        return n * factorial(n - 1)

        # Example usage
        print(factorial(5)) # 120 (5 * 4 * 3 * 2 * 1)
      

Recursive Function Tracing

Understanding how recursive calls stack up is crucial:

        # Tracing factorial(5):
        # factorial(5)
        # → 5 * factorial(4)
        # → 5 * (4 * factorial(3))
        # → 5 * (4 * (3 * factorial(2)))
        # → 5 * (4 * (3 * (2 * factorial(1))))
        # → 5 * (4 * (3 * (2 * 1)))
        # → 5 * (4 * 3 * 2)
        # → 5 * (4 * 6)
        # → 5 * 24
        # → 120
      

More Recursive Examples

1. Fibonacci Sequence

        # Recursive Fibonacci (inefficient but illustrative)
        def fibonacci(n):
        # Base cases
        if n <= 0: return 0 if n==1: return 1 # Recursive case return fibonacci(n - 1) + fibonacci(n - 2) # Example
          usage print(fibonacci(6)) # 8 

Note: The simple recursive implementation of Fibonacci has exponential time complexity O(2^n). For efficiency, you'd use dynamic programming or memoization:

            # Fibonacci with memoization
            def fibonacci_memo(n, memo=None):
            if memo is None:
            memo = {}
            if n in memo:
            return memo[n]
            if n <= 0: return 0 if n==1: return 1 memo[n]=fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
              return memo[n] # Example usage print(fibonacci_memo(50)) # Much faster for large inputs 

2. Linked List Recursion

                # Node definition
                class Node:
                def __init__(self, value):
                self.value = value
                self.next = None

                # Find length of linked list recursively
                def get_length(head):
                # Base case: empty list
                if head is None:
                return 0
                # Recursive case: count this node plus the rest
                return 1 + get_length(head.next)

                # Reverse a linked list recursively
                def reverse_list(head):
                # Base cases: empty list or only one node
                if head is None or head.next is None:
                return head
                # Recursive case
                new_head = reverse_list(head.next)
                # Reverse the pointers
                head.next.next = head
                head.next = None
                return new_head
              

Recursion vs. Iteration

It's important to understand when to use recursion versus iterative approaches:

Aspect	Recursion	Iteration
Memory Usage	Uses call stack (higher memory overhead)	Typically uses less memory
Code Clarity	Often more elegant and readable for certain problems	May be more straightforward for simple problems
Performance	Can be slower due to function call overhead	Usually faster
Stack Overflow Risk	Possible with deep recursion	Not an issue
Best For	Tree traversals, divide-and-conquer algorithms	Simple loops, performance-critical code

Iterative vs. Recursive Factorial Example

              # Recursive
              def factorial_recursive(n):
              if n == 0 or n == 1:
              return 1
              return n * factorial_recursive(n - 1)

              # Iterative
              def factorial_iterative(n):
              result = 1
              for i in range(2, n + 1):
              result *= i
              return result
            

Common Recursion Pitfalls

Missing Base Case: Leads to infinite recursion and stack overflow
Inefficient Overlapping Subproblems: Can make recursion exponentially slow
Stack Overflow: With deeply nested recursion
Unnecessary Recursion: When an iterative solution is simpler

Techniques to Improve Recursive Solutions

Memoization: Store results of subproblems to avoid redundant calculations
Tail Recursion: Special form where recursive call is the last operation
Trampolining: Technique to avoid stack overflow by simulating recursion

Practice with LeetCode Problems

Note: Previously, this course referenced the CodeSignal Arcade for practice, which is no longer available. The LeetCode problems below follow the same principles and are an excellent alternative for practicing recursion.

Basic Recursion Problems:

Fibonacci Number - Classic recursion example
Climbing Stairs - Similar to Fibonacci but with a practical context
Pow(x, n) - Implement power function using recursion

Recursive List Problems:

Reverse Linked List - Practice recursive linked list manipulation
Swap Nodes in Pairs - Intermediate linked list recursion
Merge Two Sorted Lists - Can be solved elegantly with recursion

Tree Recursion:

Maximum Depth of Binary Tree - Simple tree recursion
Same Tree - Compare two trees recursively
Path Sum - Find paths in a tree recursively