Why Recursion Exists and What Loops Cannot Express Cleanly in DSA Rust - See It Work

Why Recursion Exists and What Loops Cannot Express Cleanly

📖 Scenario: Imagine you have a set of nested boxes, each box inside another. You want to find the smallest box inside all the boxes. This is like a problem where you need to look inside each box one by one, but some boxes contain other boxes inside them. Loops can help you repeat actions, but they struggle when the number of boxes inside boxes is unknown or changes. Recursion helps by letting a function call itself to handle each smaller box until it finds the smallest one.

🎯 Goal: You will build a simple Rust program that uses recursion to find the smallest number in a nested list of numbers. This shows why recursion is useful when loops cannot easily handle nested or unknown levels of data.

📋 What You'll Learn

Create a nested vector of integers representing boxes inside boxes

Create a helper variable to track the smallest number found

Write a recursive function to find the smallest number in the nested vector

Print the smallest number found

💡 Why This Matters

🌍 Real World

Recursion is used in file system searches, parsing nested data like JSON or XML, and solving problems with hierarchical data such as organization charts or family trees.

💼 Career

Understanding recursion is essential for software developers working with complex data structures, algorithms, and tasks that involve nested or hierarchical information.

1

Create a nested vector of integers

Create a variable called nested_numbers that holds a vector with these exact elements: vec![1, 2, vec![3, 4], 5]. Use Vec where NestedNumber is an enum you define with variants Int(i32) and List(Vec).

DSA Rust

// Define enum NestedNumber with Int and List variants
// Create variable nested_numbers with vec![Int(1), Int(2), List(vec![Int(3), Int(4)]), Int(5)]
// Your code here

Hint

Define an enum called NestedNumber with two variants: Int(i32) for single numbers and List(Vec) for nested lists. Then create nested_numbers as a vector of these enum values.

2

Create a variable to track the smallest number

Inside main, create a mutable variable called smallest and set it to i32::MAX to start with the largest possible integer.

DSA Rust

enum NestedNumber {
    Int(i32),
    List(Vec),
}

fn main() {
    let nested_numbers = vec![
        NestedNumber::Int(1),
        NestedNumber::Int(2),
        NestedNumber::List(vec![NestedNumber::Int(3), NestedNumber::Int(4)]),
        NestedNumber::Int(5),
    ];
    // Create mutable variable smallest set to i32::MAX
    // Your code here
}

Hint

Use let mut smallest = i32::MAX; to start with the largest integer so you can find smaller numbers later.

3

Write a recursive function to find the smallest number

Write a function called find_smallest that takes a reference to a Vec and a mutable reference to smallest: &mut i32. It should loop over each NestedNumber in the vector. If it is Int(value), update smallest if value is smaller. If it is List(inner_vec), call find_smallest recursively on inner_vec. Call this function from main with nested_numbers and &mut smallest.

DSA Rust

enum NestedNumber {
    Int(i32),
    List(Vec),
}

fn find_smallest(numbers: &Vec, smallest: &mut i32) {
    // Your code here
}

fn main() {
    let nested_numbers = vec![
        NestedNumber::Int(1),
        NestedNumber::Int(2),
        NestedNumber::List(vec![NestedNumber::Int(3), NestedNumber::Int(4)]),
        NestedNumber::Int(5),
    ];
    let mut smallest = i32::MAX;
    // Call find_smallest here
    // Your code here
}

Hint

Use a for loop and match to check each item. If it is an integer, compare and update smallest. If it is a list, call find_smallest recursively.

4

Print the smallest number found

Add a println! statement in main to print the text "Smallest number is: {}" with the value of smallest.

DSA Rust

enum NestedNumber {
    Int(i32),
    List(Vec),
}

fn find_smallest(numbers: &Vec, smallest: &mut i32) {
    for number in numbers {
        match number {
            NestedNumber::Int(value) => {
                if *value  {
                find_smallest(inner_vec, smallest);
            }
        }
    }
}

fn main() {
    let nested_numbers = vec![
        NestedNumber::Int(1),
        NestedNumber::Int(2),
        NestedNumber::List(vec![NestedNumber::Int(3), NestedNumber::Int(4)]),
        NestedNumber::Int(5),
    ];
    let mut smallest = i32::MAX;
    find_smallest(&nested_numbers, &mut smallest);
    // Print smallest number
    // Your code here
}

Hint

Use println!("Smallest number is: {}", smallest); to show the result.

Practice

1. Why do we use recursion instead of loops in some problems?
fn factorial(n: u32) -> u32 { if n == 0 { 1 } else { n * factorial(n - 1) } }

easy

A. Recursion uses less memory than loops.

B. Loops are always slower than recursion.

C. Recursion can express problems with self-similar structure more naturally.

D. Loops cannot perform repeated actions.

Solution

1. Step 1: Understand recursion's purpose

   Recursion is useful when a problem can be broken down into smaller similar problems, like factorial.

2. Step 2: Compare recursion and loops

   Loops repeat actions but do not naturally express self-similar or nested problems as clearly as recursion.

3. Final Answer:

   Recursion can express problems with self-similar structure more naturally. -> Option C

4. Quick Check:

   Recursion = natural for self-similar problems [OK]

Hint: Recursion fits problems breaking into smaller similar parts [OK]

Common Mistakes:

• Thinking loops are always slower
• Believing recursion uses less memory
• Assuming loops cannot repeat actions

2. Which of the following is the correct Rust syntax for a recursive function that sums numbers from 1 to n?

easy

A. fn sum(n: u32) -> u32 { if n == 0 { 0 } else { n + sum(n - 1) } }

B. fn sum(n: u32) -> u32 { loop { n + sum(n - 1) } }

C. fn sum(n: u32) -> u32 { while n > 0 { n + sum(n - 1) } }

D. fn sum(n: u32) -> u32 { if n == 0 { 1 } else { n * sum(n - 1) } }

Solution

1. Step 1: Identify correct base case and recursion

   fn sum(n: u32) -> u32 { if n == 0 { 0 } else { n + sum(n - 1) } } correctly returns 0 when n is 0 and sums recursively.

2. Step 2: Check syntax and logic

   Options B and C misuse loops inside recursion, causing infinite loops or errors. fn sum(n: u32) -> u32 { if n == 0 { 1 } else { n * sum(n - 1) } } multiplies instead of sums.

3. Final Answer:

   fn sum(n: u32) -> u32 { if n == 0 { 0 } else { n + sum(n - 1) } } -> Option A

4. Quick Check:

   Correct recursion syntax = fn sum(n: u32) -> u32 { if n == 0 { 0 } else { n + sum(n - 1) } } [OK]

Hint: Look for correct base case and recursive call pattern [OK]

Common Mistakes:

• Using loops inside recursive function incorrectly
• Wrong base case value
• Mixing sum and product operations

3. What is the output of this Rust code?

fn print_numbers(n: u32) {
    if n == 0 {
        return;
    }
    print_numbers(n - 1);
    println!("{}", n);
}

fn main() {
    print_numbers(3);
}

medium

A. 1 2 3

B. 3 2 1

C. 3 3 3

D. 1 1 1

Solution

1. Step 1: Trace recursive calls

   print_numbers(3) calls print_numbers(2), then print_numbers(1), then print_numbers(0) which returns immediately.

2. Step 2: Print after recursion unwinds

   After reaching 0, the calls print 1, then 2, then 3 in order.

3. Final Answer:

   1 2 3 -> Option A

4. Quick Check:

   Recursion prints ascending after calls [OK]

Hint: Look where print happens: before or after recursive call [OK]

Common Mistakes:

• Assuming print happens before recursion
• Confusing order of prints
• Ignoring base case return

4. Identify the error in this recursive Rust function that calculates Fibonacci numbers:

fn fib(n: u32) -> u32 {
    if n == 0 {
        0
    } else if n == 1 {
        1
    } else {
        fib(n - 1) + fib(n - 2);
    }
}

medium

A. Base cases are incorrect for Fibonacci sequence.

B. Function uses loops instead of recursion.

C. Function causes infinite recursion for n=0.

D. Missing return statement in the else branch causes no value returned.

Solution

1. Step 1: Check function branches for return values

   The else branch ends with an expression but lacks a return or semicolon, causing no value returned.

2. Step 2: Understand Rust expression rules

   In Rust, the last expression without semicolon is returned. Here, semicolon after fib(n - 1) + fib(n - 2) prevents return.

3. Final Answer:

   Missing return statement in the else branch causes no value returned. -> Option D

4. Quick Check:

   Semicolon stops return in else branch [OK]

Hint: Check for semicolons ending return expressions [OK]

Common Mistakes:

• Ignoring semicolon effect on return
• Thinking base cases are wrong
• Confusing recursion with loops

5. You want to flatten a nested list of integers using recursion in Rust. Which approach best expresses this problem that loops cannot cleanly solve?

fn flatten(list: &[Nested]) -> Vec<i32> {
    // Nested is enum: Int(i32) or List(Vec<Nested>)
    // Fill this function
}

hard

A. Use a loop that only handles flat lists, ignoring nested ones.

B. Use recursion to check each element: if Int, add to result; if List, recursively flatten and extend result.

C. Use a loop with a stack to simulate recursion manually.

D. Use a single loop to iterate and flatten all nested lists without recursion.

Solution

1. Step 1: Understand nested list structure

   Nested lists can contain integers or other lists, requiring a method to explore all levels.

2. Step 2: Apply recursion to handle arbitrary depth

   Recursion naturally handles nested structures by calling itself on sublists, collecting all integers.

3. Final Answer:

   Use recursion to check each element: if Int, add to result; if List, recursively flatten and extend result. -> Option B

4. Quick Check:

   Recursion handles nested depth cleanly [OK]

Hint: Recursion fits nested structures better than flat loops [OK]

Common Mistakes:

• Trying to flatten nested lists with simple loops
• Ignoring nested depth in loops
• Using loops that skip nested elements