Introduction to Recursion

Recursion is when a function calls itself. It sounds circular, but with the right structure, it's a powerful technique for solving problems that have smaller subproblems of the same type.

What is Recursion?

A recursive function has two essential parts:

1. Base case: The condition that stops the recursion
2. Recursive case: The function calling itself with a smaller/simpler input

fn countdown(n: i32) {
    // Base case
    if n <= 0 {
        println!("Done!");
        return;
    }

    // Recursive case
    println!("{}", n);
    countdown(n - 1);
}

fn main() {
    countdown(3);
    // Output:
    // 3
    // 2
    // 1
    // Done!
}

Visualizing the Call Stack

Each recursive call adds a frame to the call stack:

countdown(3) called:

Step 1:           Step 2:           Step 3:           Step 4:
+------------+    +------------+    +------------+    +------------+
| countdown  |    | countdown  |    | countdown  |    | countdown  |
|    (0)     |    |    (0)     |    |    (0)     |    |    (0)     |
+------------+    +------------+    +------------+    +------------+
                  | countdown  |    | countdown  |
                  |    (1)     |    |    (1)     |
                  +------------+    +------------+
                                    | countdown  |
                                    |    (2)     |
                                    +------------+
                                    | countdown  |
                                    |    (3)     |
                                    +------------+

                                    Stack grows until
                                    base case reached,
                                    then unwinds.

Sum of Array

Let's solve a simple problem recursively: sum all elements in an array.

Thinking recursively:

• The sum of an empty array is 0 (base case)
• The sum of an array is the first element plus the sum of the rest

fn array_sum(arr: &[i32]) -> i32 {
    // Base case: empty array
    if arr.is_empty() {
        return 0;
    }

    // Recursive case: first + sum of rest
    arr[0] + array_sum(&arr[1..])
}

fn main() {
    let arr = [1, 2, 3, 4, 5];
    println!("{}", array_sum(&arr)); // 15
}

array_sum([1, 2, 3, 4, 5])
= 1 + array_sum([2, 3, 4, 5])
= 1 + 2 + array_sum([3, 4, 5])
= 1 + 2 + 3 + array_sum([4, 5])
= 1 + 2 + 3 + 4 + array_sum([5])
= 1 + 2 + 3 + 4 + 5 + array_sum([])
= 1 + 2 + 3 + 4 + 5 + 0
= 15

Reversing a String

fn reverse_string(s: &str) -> String {
    // Base case
    if s.len() <= 1 {
        return s.to_string();
    }

    // Recursive case: last char + reverse of rest
    let last_char = s.chars().last().unwrap();
    let rest = &s[..s.len() - last_char.len_utf8()];
    format!("{}{}", last_char, reverse_string(rest))
}

fn main() {
    println!("{}", reverse_string("hello")); // "olleh"
}

Recursion vs Iteration

Any recursive algorithm can be rewritten iteratively, and vice versa. Compare:

// Recursive
fn sum_recursive(n: i32) -> i32 {
    if n <= 0 {
        return 0;
    }
    n + sum_recursive(n - 1)
}

// Iterative
fn sum_iterative(n: i32) -> i32 {
    let mut total = 0;
    for i in 1..=n {
        total += i;
    }
    total
}

fn main() {
    println!("{}", sum_recursive(5));  // 15
    println!("{}", sum_iterative(5));  // 15
}

When to use recursion:

• Problem has natural recursive structure (trees, graphs)
• Divide and conquer algorithms
• Code clarity matters more than micro-optimization

When to use iteration:

• Simple loops suffice
• Stack space is a concern
• Performance is critical

Common Patterns

Linear Recursion

One recursive call per function invocation:

fn factorial(n: u64) -> u64 {
    if n <= 1 {
        return 1;
    }
    n * factorial(n - 1)
}

Binary Recursion (Two-Branch)

Two recursive calls, often seen in divide-and-conquer:

fn fibonacci(n: u64) -> u64 {
    if n <= 1 {
        return n;
    }
    fibonacci(n - 1) + fibonacci(n - 2)
}

Tail Recursion

The recursive call is the last operation. Some languages optimize this:

fn factorial_tail(n: u64, accumulator: u64) -> u64 {
    if n <= 1 {
        return accumulator;
    }
    factorial_tail(n - 1, n * accumulator)
}

fn factorial(n: u64) -> u64 {
    factorial_tail(n, 1)
}

How to Think Recursively

1. Identify the base case: What's the simplest version of the problem?
2. Define the recursive case: How can you reduce the problem to a smaller version?
3. Trust the recursion: Assume the recursive call works correctly
4. Combine results: Use the recursive result to solve the current problem

Example: Check if Palindrome

Problem: Is a string the same forwards and backwards?

Recursive thinking:

• Empty string or single character → palindrome (base case)
• First and last characters match, AND middle is palindrome → palindrome

fn is_palindrome(s: &str) -> bool {
    // Base case
    if s.len() <= 1 {
        return true;
    }

    // Check ends and recurse on middle
    let chars: Vec<char> = s.chars().collect();
    let first = chars[0];
    let last = chars[chars.len() - 1];

    if first != last {
        return false;
    }

    // Recurse on middle substring
    let middle: String = chars[1..chars.len() - 1].iter().collect();
    is_palindrome(&middle)
}

fn main() {
    println!("{}", is_palindrome("racecar")); // true
    println!("{}", is_palindrome("hello"));   // false
}

Example: Power Function

Calculate x^n recursively:

fn power(x: f64, n: i32) -> f64 {
    // Base case
    if n == 0 {
        return 1.0;
    }

    // Handle negative exponents
    if n < 0 {
        return 1.0 / power(x, -n);
    }

    // Recursive case
    x * power(x, n - 1)
}

fn main() {
    println!("{}", power(2.0, 10)); // 1024.0
}

Optimized with divide and conquer (O(log n) instead of O(n)):

fn power_fast(x: f64, n: i32) -> f64 {
    if n == 0 {
        return 1.0;
    }
    if n < 0 {
        return 1.0 / power_fast(x, -n);
    }

    let half = power_fast(x, n / 2);

    if n % 2 == 0 {
        half * half
    } else {
        half * half * x
    }
}

fn main() {
    println!("{}", power_fast(2.0, 10)); // 1024.0
}

Debugging Recursion

Add tracing to understand execution flow:

fn factorial_debug(n: u64, depth: usize) -> u64 {
    let indent = "  ".repeat(depth);
    println!("{}factorial({})", indent, n);

    if n <= 1 {
        println!("{}returning 1", indent);
        return 1;
    }

    let result = n * factorial_debug(n - 1, depth + 1);
    println!("{}returning {}", indent, result);
    result
}

fn main() {
    factorial_debug(4, 0);
}

Output:

factorial(4)
  factorial(3)
    factorial(2)
      factorial(1)
      returning 1
    returning 2
  returning 6
returning 24

Common Mistakes

1. Missing Base Case

fn infinite_recursion(n: i32) -> i32 {
    // Oops, no base case!
    n + infinite_recursion(n - 1)
}
// This will crash with stack overflow

2. Base Case Never Reached

fn never_ends(n: i32) -> i32 {
    if n == 0 {
        return 0;
    }
    n + never_ends(n + 1)  // Going wrong direction!
}

3. Not Making Progress

fn no_progress(arr: &[i32]) -> i32 {
    if arr.is_empty() {
        return 0;
    }
    arr[0] + no_progress(arr)  // Same array, not &arr[1..]!
}

Recursion in Data Structures

Recursive thinking is natural for recursive data structures:

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

// Sum all values in tree
fn tree_sum(node: &Option<Box<TreeNode>>) -> i32 {
    match node {
        None => 0,
        Some(n) => {
            n.val + tree_sum(&n.left) + tree_sum(&n.right)
        }
    }
}

Key Takeaways

1. Recursion = function calling itself with simpler input
2. Every recursive function needs a base case
3. Each call adds a frame to the call stack
4. Think: "If I solve the smaller problem, how do I use that solution?"
5. Recursion is elegant for trees, divide-and-conquer, and backtracking
6. Be mindful of stack limits and efficiency
7. Any recursion can be converted to iteration (and vice versa)

Recursion is a fundamental technique that will appear throughout algorithms—in sorting, tree traversal, dynamic programming, and backtracking. Master the basics here, and you'll be ready for more advanced recursive patterns.