Fibonacci Using Recursion in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the base case in a recursive Fibonacci function?

The base case returns the first two Fibonacci numbers directly, usually when n is 0 or 1, to stop further recursion.

beginner

Explain why recursion is a natural fit for calculating Fibonacci numbers.

Because each Fibonacci number is the sum of the two previous ones, recursion naturally expresses this by calling the function for n-1 and n-2.

intermediate

What is the time complexity of the naive recursive Fibonacci algorithm?

It is exponential, specifically O(2^n), because it recalculates the same Fibonacci numbers many times.

beginner

Show the Rust function signature for a recursive Fibonacci function.

fn fibonacci(n: u32) -> u32

intermediate

What happens if you call the recursive Fibonacci function with n = 5? Describe the calls.

The function calls fibonacci(4) and fibonacci(3), then fibonacci(4) calls fibonacci(3) and fibonacci(2), and so on, breaking down until base cases are reached.

What does the base case in a recursive Fibonacci function usually check?

A If n is 0 or 1

B If n is negative

C If n is greater than 10

D If n is even

The base case returns the Fibonacci number directly when n is 0 or 1 to stop recursion.

What is the main problem with the naive recursive Fibonacci implementation?

A It uses too much memory

B It recalculates the same values multiple times

C It does not return correct results

D It only works for even numbers

The naive recursion recalculates Fibonacci numbers repeatedly, causing exponential time complexity.

Which Rust keyword is used to define a function?

A func

B def

C fn

D function

In Rust, functions are defined using the 'fn' keyword.

What is the return type of a Fibonacci function that takes a u32 in Rust?

A u32

B i32

C usize

D bool

The function returns a u32 to match the input type and represent Fibonacci numbers.

How many times is fibonacci(1) called when calculating fibonacci(5) recursively?

A 1

B 2

C 3

D 5

fibonacci(1) is called 5 times during the recursive calls for fibonacci(5).

Describe how recursion works in the Fibonacci function and why base cases are important.

Think about how the function breaks down the problem into smaller parts.

Explain the drawbacks of the naive recursive Fibonacci approach and suggest a way to improve it.

Consider how to avoid recalculating the same Fibonacci numbers.

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