Fibonacci Using Recursion in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci Recursive Call

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

DSA Rust

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

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

A 5

B 8

C 3

D 13

💡 Hint

Remember that Fibonacci sequence starts with 0, 1, 1, 2, 3, 5...

The Fibonacci sequence starts with 0 and 1. fibonacci(5) returns the 5th number in the sequence, which is 5.

❓ Predict Output

intermediate

Output of Fibonacci Recursive Call with n=7

What is the output of this Rust code that calculates the 7th Fibonacci number recursively?

DSA Rust

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

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

A 8

B 13

C 21

D 34

💡 Hint

Count the Fibonacci numbers starting from 0: 0,1,1,2,3,5,8,13...

The 7th Fibonacci number (starting from 0) is 13.

🧠 Conceptual

advanced

Understanding Recursive Calls in Fibonacci

How many total calls to the fibonacci function are made when calculating fibonacci(4) using the recursive function below?

DSA Rust

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

A 15

B 7

C 5

D 9

💡 Hint

Draw the recursive call tree for fibonacci(4).

The call tree for fibonacci(4) has 9 total calls including repeated calls.

🔧 Debug

advanced

Identify the Runtime Error in Fibonacci Code

What error will this Rust code produce when run, and why?

DSA Rust

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

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

A Outputs 0 without error

B Compile-time error: mismatched types

C Stack overflow due to infinite recursion

D Runtime panic: index out of bounds

💡 Hint

Consider what happens when n is negative in the recursive calls.

The function never reaches the base case for negative n, causing infinite recursion and stack overflow.

🚀 Application

expert

Optimizing Fibonacci with Memoization

Which Rust code snippet correctly implements memoization to optimize the recursive Fibonacci function?

A

fn fibonacci(n: usize, memo: &mut Vec<u64>) -> u64 {
    if n <= 1 {
        return n as u64;
    }
    if memo[n] != 0 {
        return memo[n];
    }
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    memo[n]
}

fn main() {
    let n = 10;
    let mut memo = vec![0; n + 1];
    println!("{}", fibonacci(n, &mut memo));
}

B

fn fibonacci(n: usize) -> u64 {
    let mut memo = vec![0; n + 1];
    if n <= 1 {
        return n as u64;
    }
    memo[0] = 0;
    memo[1] = 1;
    for i in 2..=n {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    memo[n]
}

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

C

fn fibonacci(n: usize, memo: &mut Vec<Option<u64>>) -> u64 {
    if let Some(val) = memo[n] {
        return val;
    }
    if n <= 1 {
        memo[n] = Some(n as u64);
    } else {
        memo[n] = Some(fibonacci(n - 1, memo) + fibonacci(n - 2, memo));
    }
    memo[n].unwrap()
}

fn main() {
    let n = 10;
    let mut memo = vec![None; n + 1];
    println!("{}", fibonacci(n, &mut memo));
}

D

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

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

💡 Hint

Memoization stores results to avoid repeated calculations. Check how memo is used and initialized.

Option A uses a mutable vector initialized with zeros and checks if a value is already computed before recursive calls.

Practice

1. What does the Fibonacci sequence represent when calculated using recursion?

easy

A. Each number is the square of the previous number

B. Each number is the product of the two preceding numbers

C. Each number is the difference of the two preceding numbers

D. Each number is the sum of the two preceding numbers

Solution

1. Step 1: Understand Fibonacci sequence definition

   The Fibonacci sequence is defined such that each number is the sum of the two numbers before it.

2. Step 2: Relate to recursion

   Recursion calls the function for the two previous numbers and adds their results.

3. Final Answer:

   Each number is the sum of the two preceding numbers -> Option D

4. Quick Check:

   Fibonacci = sum of two previous numbers [OK]

Hint: Fibonacci adds last two numbers, not multiply or subtract [OK]

Common Mistakes:

• Thinking Fibonacci multiplies previous numbers
• Confusing subtraction or division with addition
• Assuming Fibonacci squares previous number

2. Which of the following is the correct Rust function signature for a recursive Fibonacci function?

easy

A. fn fibonacci(n: i32) -> i32

B. fn fibonacci(n) -> i32

C. fn fibonacci(n: i32)

D. fn fibonacci(n: i32) -> void

Solution

1. Step 1: Check Rust function signature syntax

   Rust requires parameter types and return type specified, e.g., fn name(param: type) -> return_type.

2. Step 2: Match correct signature for Fibonacci

   Fibonacci takes an integer and returns an integer, so fn fibonacci(n: i32) -> i32 is correct.

3. Final Answer:

   fn fibonacci(n: i32) -> i32 -> Option A

4. Quick Check:

   Rust needs types and return type [OK]

Hint: Rust functions need parameter and return types declared [OK]

Common Mistakes:

• Omitting parameter type
• Missing return type
• Using void instead of () or proper return type

3. What is the output of this Rust code?

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

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

medium

A. 3

B. 5

C. 8

D. 13

Solution

1. Step 1: Trace fibonacci(5) calls

   fibonacci(5) = fibonacci(4) + fibonacci(3). Breaking down recursively, fibonacci(5) = 5.

2. Step 2: Confirm base cases and sums

   Base cases: fibonacci(0)=0, fibonacci(1)=1. Summing up gives fibonacci(5) = 5.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Fibonacci(5) = 5 [OK]

Hint: Remember fibonacci(5) = 5 from sequence 0,1,1,2,3,5 [OK]

Common Mistakes:

• Confusing fibonacci(5) with fibonacci(6)
• Miscounting base cases
• Adding wrong recursive results

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

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

medium

A. The base cases are incorrect

B. The function will cause infinite recursion

C. The recursive step uses subtraction instead of addition

D. The function lacks a return type

Solution

1. Step 1: Check base cases

   Base cases for n=0 and n=1 return 0 and 1 correctly.

2. Step 2: Analyze recursive step

   The recursive step uses subtraction (fibonacci(n - 1) - fibonacci(n - 2)) instead of addition, which is incorrect for Fibonacci.

3. Final Answer:

   The recursive step uses subtraction instead of addition -> Option C

4. Quick Check:

   Fibonacci sums previous two, not subtracts [OK]

Hint: Fibonacci recursion adds two previous calls, not subtracts [OK]

Common Mistakes:

• Using subtraction in recursive step
• Forgetting to return values
• Incorrect base case values

5. How can you optimize the recursive Fibonacci function in Rust to avoid repeated calculations?

hard

A. Use memoization to store and reuse computed results

B. Increase the recursion depth limit

C. Use a loop instead of recursion

D. Call the function with negative numbers

Solution

1. Step 1: Understand recursion inefficiency

   Recursive Fibonacci recalculates the same values many times, causing slow performance.

2. Step 2: Apply memoization

   Memoization stores results of previous calls in a cache to reuse, avoiding repeated work.

3. Final Answer:

   Use memoization to store and reuse computed results -> Option A

4. Quick Check:

   Memoization optimizes recursion by caching [OK]

Hint: Cache results to speed up recursive Fibonacci [OK]

Common Mistakes:

• Increasing recursion depth doesn't fix repeated work
• Using loops changes approach, not recursion optimization
• Calling with negative numbers causes errors