Recursion Concept and Call Stack Visualization in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is recursion in programming?

Recursion is when a function calls itself to solve smaller parts of a problem until it reaches a simple case it can solve directly.

beginner

What is a base case in recursion?

A base case is the simplest situation in a recursive function that stops the recursion by returning a direct answer without calling itself again.

intermediate

How does the call stack help in recursion?

The call stack keeps track of all the active function calls. Each recursive call adds a new layer to the stack, and when a base case is reached, the stack unwinds as functions return their results.

beginner

Rust recursive function example: What does this function do? fn factorial(n: u32) -> u32 { if n == 0 { 1 } else { n * factorial(n - 1) } }

This function calculates the factorial of a number n. It multiplies n by the factorial of n-1 until it reaches 0, where it returns 1 as the base case.

intermediate

What happens if a recursive function has no base case?

Without a base case, the recursive calls never stop, causing the program to run forever or crash with a stack overflow error.

What is the purpose of the base case in recursion?

A To call the function again

B To stop the recursion and return a simple answer

C To increase the call stack size

D To make the function run faster

The base case stops recursion by providing a direct answer without further calls.

In Rust, what does this recursive function compute? fn sum(n: u32) -> u32 { if n == 0 { 0 } else { n + sum(n - 1) } }

A Fibonacci number at position n

B Factorial of n

C Sum of numbers from 1 to n

D Product of numbers from 1 to n

The function adds n to the sum of numbers below it until 0, calculating the sum from 1 to n.

What does the call stack do during recursion?

A Runs all calls in parallel

B Deletes previous calls immediately

C Prevents recursion from happening

D Stores each recursive call until base case is reached

The call stack stores each active call so the program can return results in order.

What error occurs if recursion never reaches a base case?

A Stack overflow

B Syntax error

C Type error

D Memory leak

Without a base case, calls pile up until the call stack runs out of space, causing a stack overflow.

Which of these is a correct base case for a factorial function?

A if n == 0 { return 1 }

B if n == 1 { return 0 }

C if n > 0 { return n }

D if n < 0 { return n }

Factorial of 0 is 1, so this base case stops recursion correctly.

Explain how recursion works using the example of calculating factorial of 3.

Think about how factorial(3) calls factorial(2), then factorial(1), then factorial(0).

Describe the role of the call stack in managing recursive function calls.

Imagine stacking plates; each call adds a plate, and returning removes one.

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