12.1 Recursion basics

Recursion is a powerful programming technique that breaks complex problems into simpler subproblems. By calling a function within itself, recursion solves each subproblem until reaching a base case, then combines the results to solve the original problem.

Writing recursive functions requires careful consideration of base cases and recursive cases. Tracing recursive algorithm execution helps understand how the function works, while optimization techniques like memoization can improve performance. Recursion is a valuable tool for solving complex problems efficiently.

Recursion Fundamentals

Recursion for problem simplification

Top images from around the web for Recursion for problem simplification

• 

  CS 201: Lecture 20: Recursion View original

  Is this image relevant?

• 

  Reading 10: Recursion View original

  Is this image relevant?

• 

  Reading 10: Recursion View original

  Is this image relevant?

• 

  CS 201: Lecture 20: Recursion View original

  Is this image relevant?

• 

  Reading 10: Recursion View original

  Is this image relevant?

1 of 3

Top images from around the web for Recursion for problem simplification

• 

  CS 201: Lecture 20: Recursion View original

  Is this image relevant?

• 

  Reading 10: Recursion View original

  Is this image relevant?

• 

  Reading 10: Recursion View original

  Is this image relevant?

• 

  CS 201: Lecture 20: Recursion View original

  Is this image relevant?

• 

  Reading 10: Recursion View original

  Is this image relevant?

1 of 3

• Recursion breaks down complex problems into simpler subproblems
  • Divides original problem into smaller, more manageable parts
  • Solves each subproblem recursively by calling the same function
  • Combines solutions of subproblems to solve the original problem
• Recursive functions consist of two main components:
  • Base case: simple, non-recursive condition that terminates recursion (empty list, zero, one)
  • Recursive case: condition that calls the function itself with a simpler input (smaller list, reduced number)
• Calculating factorial of a number $n$ recursively (4!, 5!)
  • Factorial of $n$ defined as $n! = n \times (n-1) \times (n-2) \times ... \times 2 \times 1$
  • Base case: $n = 0$ or $n = 1$, factorial is defined as 1
  • Recursive case: breaks down problem into simpler version by calculating $n! = n \times (n-1)!$
• Recursion often employs a divide and conquer strategy to solve problems

Writing recursive functions

• Recursive functions must have a base case to avoid infinite recursion
  • Base case: condition that causes function to return without further recursive calls
  • Typically the simplest possible input for the function (empty list, zero, one)
• Recursive case: function calls itself with a modified input
  • Modified input should move closer to base case with each recursive call (smaller list, reduced number)
  • Ensures function will eventually reach base case and terminate
• Recursive function to calculate sum of numbers from 1 to $n$

[def](https://www.fiveableKeyTerm:def) sum_recursive(n):
    if n == 1:  # Base case
        return 1
    else:  # Recursive case
        return n + sum_recursive(n - 1)

• Tail recursion is a specific form where the recursive call is the last operation in the function

Tracing recursive algorithm execution

• Tracing execution helps understand how recursive function works
  • Keeps track of each function call and corresponding return value
  • Function calls represented in a call stack, most recent call at the top
• When recursive function called, added to top of call stack
  • If base case met, function returns value and is removed from stack
  • If recursive case met, new function call added to top of stack
• Return values passed back through call stack as each function call completes
• Tracing execution of recursive factorial function for $n = 4$

factorial(4)
  ├── 4 * factorial(3)
         ├── 3 * factorial(2)
                ├── 2 * factorial(1)
                       ├── 1 (base case)
                ├── 2 * 1 = 2
         ├── 3 * 2 = 6
  ├── 4 * 6 = 24

Optimization and Performance Considerations

• Recursion can lead to stack overflow errors if the call stack becomes too large
• Memoization can improve performance by storing results of expensive function calls
• Iteration is often an alternative to recursion, potentially offering better performance in some cases