Fibonacci Using Recursion in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define the base case for the Fibonacci recursion.

DSA Rust

fn fibonacci(n: u32) -> u32 {
    if n == [1] {
        return n;
    }
    fibonacci(n - 1) + fibonacci(n - 2)
}

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

A3

B1

C2

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 as the only base case causes infinite recursion for n=0.

Forgetting to return n in the base case.

The base case for Fibonacci recursion is when n is 0, returning 0.

2fill in blank

medium

Complete the code to add the second base case for the Fibonacci recursion.

DSA Rust

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

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

A1

B3

C2

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 2 instead of 1 as the second base case.

Using AND instead of OR in the condition.

The second base case is when n is 1, returning 1.

3fill in blank

hard

Fix the error in the recursive calls to correctly compute Fibonacci numbers.

DSA Rust

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

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

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' causes infinite recursion.

Using '*' or '/' causes wrong results.

The recursive call should subtract 1 from n to get the previous Fibonacci number.

4fill in blank

hard

Fill both blanks to complete the recursive Fibonacci function correctly.

DSA Rust

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

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

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' in one or both recursive calls.

Using multiplication or division operators.

Both recursive calls subtract 1 and 2 respectively to get previous Fibonacci numbers.

5fill in blank

hard

Fill all three blanks to create a recursive Fibonacci function with memoization using a mutable cache.

DSA Rust

use std::collections::HashMap;

fn fibonacci(n: u32, cache: &mut HashMap<u32, u32>) -> u32 {
    if n == 0 || n == 1 {
        return n;
    }
    if cache.contains_key(&n) {
        return cache.get(&n).copied().unwrap();
    }
    let result = fibonacci(n [1] 1, cache) + fibonacci(n [2] 2, cache);
    cache.insert(n, result);
    return [3];
}

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

A-

B+

Cresult

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' instead of '-' in recursive calls.

Returning n instead of the computed result.

Use subtraction for recursive calls and return the computed result after caching.

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