Chapter 26: R Function Recursion

Part 1: What is Recursion?

Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller instances of the same problem.

The Two Essential Parts of Every Recursive Function

Every recursive function must have:

1. Base Case: A condition that stops the recursion (the smallest doll)

2. Recursive Case: The function calling itself with a smaller version of the problem

The Basic Structure

Part 2: Classic Examples of Recursion

Example 1: Factorial – The “Hello World” of Recursion

The factorial of n (written as n!) is the product of all positive integers less than or equal to n:

• 5! = 5 × 4 × 3 × 2 × 1 = 120

• 3! = 3 × 2 × 1 = 6

• 1! = 1

• 0! = 1 (by definition)

Output with tracing:

Let’s trace through what happens:

1. factorial_recursive(5) calls 5 * factorial_recursive(4)

2. factorial_recursive(4) calls 4 * factorial_recursive(3)

3. factorial_recursive(3) calls 3 * factorial_recursive(2)

4. factorial_recursive(2) calls 2 * factorial_recursive(1)

5. factorial_recursive(1) hits base case, returns 1

6. Then it unwinds: 2 × 1 = 2, 3 × 2 = 6, 4 × 6 = 24, 5 × 24 = 120

Example 2: Fibonacci Sequence

The Fibonacci sequence starts with 0, 1, and each subsequent number is the sum of the two preceding ones:
0, 1, 1, 2, 3, 5, 8, 13, 21, …

Output:

Visualizing the Recursive Calls for Fibonacci

Part 3: Understanding the Call Stack

Every recursive call adds a new frame to the call stack. When base cases are reached, the stack unwinds.

Visualizing the Stack

Output:

Part 4: More Practical Examples

Example 1: Sum of a Vector (Without Using sum())

Example 2: Finding Maximum Value in a Vector

Example 3: Power Function (x^n)

Example 4: Binary Search

Example 5: Directory Tree Traversal

Part 5: Tree Recursion and Data Structures

Example: Binary Tree Traversal

Example: Calculate Tree Properties

Part 6: Recursion vs. Iteration

Comparison with Factorial

When to Use Recursion vs. Iteration

Part 7: Optimizing Recursion

Problem: Inefficient Fibonacci

The naive Fibonacci is extremely inefficient because it recalculates the same values many times:

Solution 1: Memoization

Solution 2: Tail Recursion

Tail recursion is when the recursive call is the last operation. R doesn’t optimize tail recursion, but it’s a good concept to understand:

Part 8: Common Recursion Patterns

Pattern 1: Divide and Conquer

Pattern 2: Backtracking

Pattern 3: Mutual Recursion

Part 9: Common Pitfalls and Solutions

Pitfall 1: Missing Base Case

Pitfall 2: Base Case Never Reached

Pitfall 3: Stack Overflow for Deep Recursion

Pitfall 4: Inefficient Recursion

Part 10: Performance Considerations

Measuring Recursion Depth

Time Complexity Comparison

Summary: The Recursion Philosophy

Recursion is your tool for solving problems that have a self-similar structure. Master these patterns:

1. Linear recursion – One recursive call (factorial, sum)

2. Tree recursion – Multiple recursive calls (Fibonacci, tree traversal)

3. Divide and conquer – Split problem into halves

4. Backtracking – Try all possibilities

5. Mutual recursion – Functions calling each other

Essential components of every recursive function:

• Base case(s) – When to stop

• Recursive case – How to break down the problem

• Progress toward base case – Each call must get closer to stopping

Pros of recursion:

• Elegant, mathematical solutions

• Natural for recursive data structures (trees, nested lists)

• Often simpler and more readable

Cons of recursion:

• Can be slower (function call overhead)

• Risk of stack overflow for deep recursion

• Can be harder to debug

• Not always intuitive

When to use recursion:

• Tree/graph traversal

• Divide-and-conquer algorithms

• Backtracking problems

• Mathematical definitions (factorial, Fibonacci)

• Processing nested structures

When NOT to use recursion:

• Simple iterative problems

• Very deep recursion (thousands of levels)

• Performance-critical code

• When stack overflow is a concern

Recursion transforms how you think about problems. Instead of thinking “how do I loop through this?”, you start thinking “how is this problem a smaller version of itself?” It’s a shift from imperative to declarative thinking, and it’s one of the most beautiful concepts in computer science.

Would you like me to elaborate on any specific aspect of recursion or explore more complex recursive algorithms?