Recursion Concept and Call Stack Visualization in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to make the function call itself recursively.

DSA Rust

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

Drag options to blanks, or click blank then click option'

A1

B0

Cn - 1

Dn + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 causes infinite recursion.

Using 0 or 1 directly in the recursive call breaks the logic.

The function calls itself with n - 1 to reduce the problem size until it reaches 0.

2fill in blank

medium

Complete the code to correctly calculate the nth Fibonacci number recursively.

DSA Rust

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

Drag options to blanks, or click blank then click option'

An - 2

Bn - 1

Cn + 1

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n - 2 for both calls.

Using n + 1 causes infinite recursion.

The Fibonacci number is the sum of the two previous numbers: fibonacci(n-1) + fibonacci(n-2).

3fill in blank

hard

Fix the error in the recursive function to avoid infinite recursion.

DSA Rust

fn countdown(n: i32) {
    if n == 0 {
        println!("Blast off!");
    } else {
        println!("{}", n);
        countdown([1]);
    }
}

Drag options to blanks, or click blank then click option'

An - 1

B0

Cn + 1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 causes infinite recursion.

Calling with n does not change the state.

The function must call countdown with n - 1 to move towards the base case and stop recursion.

4fill in blank

hard

Fill both blanks to create a recursive function that sums numbers from 1 to n.

DSA Rust

fn sum_to_n(n: u32) -> u32 {
    if n == 0 {
        0
    } else {
        n + sum_to_n([1])
    }
}

fn main() {
    let result = sum_to_n([2]);
    println!("Sum is {}", result);
}

Drag options to blanks, or click blank then click option'

An - 1

Bn + 1

C5

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 in recursion causes infinite loop.

Calling sum_to_n with 0 in main returns 0 immediately.

The recursive call reduces n by 1 each time, and the main function calls sum_to_n with 5 to sum 1 through 5.

5fill in blank

hard

Fill all three blanks to create a recursive function that reverses a string.

DSA Rust

fn reverse_string(s: &str) -> String {
    if s.is_empty() {
        String::new()
    } else {
        let first_char = s.chars().next().unwrap();
        let rest = &s[[1]..];
        format!("{}{}", reverse_string(rest), [2])
    }
}

fn main() {
    let word = "hello";
    let reversed = reverse_string([3]);
    println!("Reversed: {}", reversed);
}

Drag options to blanks, or click blank then click option'

A1

Bfirst_char

Cword

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 in slice causes infinite recursion.

Appending the whole string instead of first_char breaks reversal.

The function slices the string from index 1 to end, recursively reverses it, then appends the first character. The main function passes the original word.

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