Recursion Concept and Call Stack Visualization in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Factorial Function

What is the output of this Rust code that calculates factorial using recursion?

DSA Rust

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

fn main() {
    println!("{}", factorial(4));
}

A 120

B 1

C 10

D 24

💡 Hint

Recall factorial of 4 is 4 * 3 * 2 * 1.

The factorial function multiplies n by factorial of n-1 until n is 0. factorial(4) = 4*3*2*1 = 24.

❓ Predict Output

intermediate

Output of Recursive Fibonacci Function

What is the output of this Rust code that calculates the 5th Fibonacci number using recursion?

DSA Rust

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

fn main() {
    println!("{}", fibonacci(5));
}

A 3

B 5

C 8

D 13

💡 Hint

Fibonacci sequence starts 0,1,1,2,3,5,...

The 5th Fibonacci number (0-based) is 5: fibonacci(5) = fibonacci(4) + fibonacci(3) = 3 + 2 = 5.

❓ Predict Output

advanced

Output of Recursive Sum of Array Elements

What is the output of this Rust code that recursively sums elements of an array slice?

DSA Rust

fn sum_slice(arr: &[i32]) -> i32 {
    if arr.is_empty() {
        0
    } else {
        arr[0] + sum_slice(&arr[1..])
    }
}

fn main() {
    let numbers = [2, 4, 6, 8];
    println!("{}", sum_slice(&numbers));
}

A 20

B 24

C 16

D 18

💡 Hint

Sum all elements: 2 + 4 + 6 + 8.

The function adds the first element and recursively sums the rest. Total is 2+4+6+8=20.

❓ Predict Output

advanced

Output of Recursive String Reverse Function

What is the output of this Rust code that reverses a string recursively?

DSA Rust

fn reverse_string(s: &str) -> String {
    if s.is_empty() {
        String::new()
    } else {
        let (first, rest) = s.split_at(1);
        format!("{}{}", reverse_string(rest), first)
    }
}

fn main() {
    println!("{}", reverse_string("rust"));
}

A tsur

B rust

C trus

D urts

💡 Hint

The function moves first character to the end recursively.

The function takes first character and appends it after reversing the rest, so "rust" becomes "tsur".

❓ Predict Output

expert

Output of Recursive Tower of Hanoi Moves

What is the output of this Rust code that prints moves to solve Tower of Hanoi for 3 disks?

DSA Rust

fn tower_of_hanoi(n: u32, from: char, to: char, aux: char) {
    if n == 1 {
        println!("Move disk 1 from {} to {}", from, to);
    } else {
        tower_of_hanoi(n - 1, from, aux, to);
        println!("Move disk {} from {} to {}", n, from, to);
        tower_of_hanoi(n - 1, aux, to, from);
    }
}

fn main() {
    tower_of_hanoi(3, 'A', 'C', 'B');
}

A ["Move disk 1 from A to C", "Move disk 2 from B to A", "Move disk 1 from C to B", "Move disk 3 from A to C", "Move disk 1 from B to C", "Move disk 2 from A to B", "Move disk 1 from C to A"]

B ["Move disk 1 from A to B", "Move disk 2 from A to C", "Move disk 1 from B to C", "Move disk 3 from A to B", "Move disk 1 from C to A", "Move disk 2 from C to B", "Move disk 1 from A to B"]

C ["Move disk 1 from A to C", "Move disk 2 from A to B", "Move disk 1 from C to B", "Move disk 3 from A to C", "Move disk 1 from B to A", "Move disk 2 from B to C", "Move disk 1 from A to C"]

D ["Move disk 1 from A to B", "Move disk 2 from B to C", "Move disk 1 from A to C", "Move disk 3 from A to C", "Move disk 1 from C to B", "Move disk 2 from C to A", "Move disk 1 from B to A"]

💡 Hint

Follow the recursive pattern: move n-1 disks to auxiliary, move largest disk, then move n-1 disks to target.

The Tower of Hanoi solution for 3 disks follows a specific sequence of moves as shown in option C.

Practice

1. What happens when a recursive function calls itself without a base case?

easy

A. The function converts into a loop automatically.

B. The function returns immediately without doing anything.

C. The function runs only once and stops.

D. It causes infinite recursion leading to a stack overflow error.

Solution

1. Step 1: Understand recursion base case role

   The base case stops recursion by providing a condition to end calls.

2. Step 2: Analyze missing base case effect

   Without a base case, the function keeps calling itself endlessly, filling the call stack.

3. Final Answer:

   It causes infinite recursion leading to a stack overflow error. -> Option D

4. Quick Check:

   Missing base case = infinite recursion [OK]

Hint: Always check for a base case to stop recursion [OK]

Common Mistakes:

• Thinking recursion stops automatically
• Assuming function returns without base case
• Confusing recursion with loops

2. Which of the following is the correct syntax to define a recursive function in Rust that calculates factorial of a number n?

easy

A. fn factorial(n: u32) { if n == 0 { 1 } else { n * factorial(n - 1) } }

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

C. fn factorial(n: u32) -> u32 { while n > 0 { n * factorial(n - 1) } }

D. fn factorial(n: u32) -> u32 { return n * factorial(n + 1); }

Solution

1. Step 1: Check function return type and base case

   fn factorial(n: u32) -> u32 { if n == 0 { 1 } else { n * factorial(n - 1) } } correctly returns u32 and has base case for n == 0 returning 1.

2. Step 2: Verify recursive call correctness

   fn factorial(n: u32) -> u32 { if n == 0 { 1 } else { n * factorial(n - 1) } } calls factorial(n - 1) correctly; others miss return type or have wrong logic.

3. Final Answer:

   fn factorial(n: u32) -> u32 { if n == 0 { 1 } else { n * factorial(n - 1) } } -> Option B

4. Quick Check:

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

Hint: Look for base case and correct return type in Rust function [OK]

Common Mistakes:

• Omitting return type in function signature
• Using while loop inside recursive function
• Calling factorial with n + 1 causing infinite recursion

3. What is the output of the following 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: Understand print order after recursion

   After reaching base case, prints happen in reverse call order: prints 1, then 2, then 3.

3. Final Answer:

   1 2 3 -> Option A

4. Quick Check:

   Recursion prints after calls = 1 2 3 [OK]

Hint: Print after recursive call prints in ascending order [OK]

Common Mistakes:

• Assuming prints happen before recursive call
• Confusing order of execution in recursion
• Ignoring base case effect

4. Identify the error in this Rust recursive function that calculates the sum of numbers from 1 to n:

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

medium

A. The base case condition should be n == 0, not n == 1.

B. The function lacks a return statement in the else block.

C. The recursive call uses n + 1 instead of n - 1, causing infinite recursion.

D. The function should use a loop instead of recursion.

Solution

1. Step 1: Analyze recursive call parameter

   The function calls sum(n + 1), which increases n, moving away from base case.

2. Step 2: Understand effect on recursion

   Since n grows, base case n == 1 is never reached, causing infinite recursion and stack overflow.

3. Final Answer:

   The recursive call uses n + 1 instead of n - 1, causing infinite recursion. -> Option C

4. Quick Check:

   Recursive call must reduce n to reach base case [OK]

Hint: Recursive calls should move toward base case by decreasing n [OK]

Common Mistakes:

• Using n + 1 instead of n - 1 in recursion
• Confusing base case condition
• Missing return keyword in else block

5. Given the following Rust recursive function that reverses a string slice, what will be the output of reverse("rust")?

fn reverse(s: &str) -> String {
    if s.is_empty() {
        String::new()
    } else {
        let (first, rest) = s.split_at(1);
        format!("{}{}", reverse(rest), first)
    }
}

fn main() {
    println!("{}", reverse("rust"));
}

hard

A. "tsur"

B. "rust"

C. "trus"

D. "rustt"

Solution

1. Step 1: Understand recursion and string splitting

   The function splits the string into first character and rest, then recursively reverses rest and appends first.

2. Step 2: Trace calls for "rust"

   reverse("rust") calls reverse("ust") + "r", reverse("ust") calls reverse("st") + "u", and so on, building reversed string "tsur".

3. Final Answer:

   "tsur" -> Option A

4. Quick Check:

   Recursive reverse builds string backwards = "tsur" [OK]

Hint: Recursive reverse appends first char after reversing rest [OK]

Common Mistakes:

• Confusing order of concatenation
• Not handling empty string base case
• Assuming original string is returned