Fibonacci Using Recursion in DSA Rust

Mental Model

Calculate each Fibonacci number by adding the two before it, using a function that calls itself.

Analogy: Like climbing stairs where to reach step n, you first need to know how you got to step n-1 and n-2.

fib(4)
  /    \
fib(3)  fib(2)
 /  \     /  \
fib(2) fib(1) fib(1) fib(0)
 /  \
fib(1) fib(0)

Dry Run Walkthrough

Input: Calculate fib(4)

Goal: Find the 4th Fibonacci number using recursion

Step 1: Call fib(4), which calls fib(3) and fib(2)

fib(4) -> fib(3) + fib(2)

Why: To find fib(4), we need fib(3) and fib(2)

Step 2: fib(3) calls fib(2) and fib(1)

fib(3) -> fib(2) + fib(1), fib(2) -> fib(1) + fib(0)

Why: fib(3) breaks down into smaller Fibonacci calls

Step 3: fib(2) calls fib(1) and fib(0), both return 1 and 0 respectively

fib(2) = 1 + 0 = 1

Why: Base cases fib(1) and fib(0) return fixed values

Step 4: fib(1) returns 1 directly

fib(3) = fib(2) + fib(1) = 1 + 1 = 2

Why: fib(1) is a base case

Step 5: fib(2) calls fib(1) and fib(0) again, returns 1

fib(2) = 1

Why: fib(2) calculation repeated for fib(4) right side

Step 6: Add fib(3) and fib(2) results: 2 + 1

fib(4) = 3

Why: Final sum gives the 4th Fibonacci number

Result:

fib(4) = 3

Annotated Code

DSA Rust

fn fib(n: u32) -> u32 {
    if n == 0 {
        return 0; // base case: fib(0) = 0
    } else if n == 1 {
        return 1; // base case: fib(1) = 1
    }
    fib(n - 1) + fib(n - 2) // recursive call adding previous two Fibonacci numbers
}

fn main() {
    let n = 4;
    let result = fib(n);
    println!("fib({}) = {}", n, result);
}

if n == 0 { return 0; } else if n == 1 { return 1; }

handle base cases to stop recursion

fib(n - 1) + fib(n - 2)

recursive call to sum previous two Fibonacci numbers

Output

fib(4) = 3

Complexity Analysis

Time: O(2^n) because each call splits into two more calls, doubling work exponentially

Space: O(n) due to the maximum depth of the recursion call stack being n

vs Alternative: Iterative approach is O(n) time and O(1) space, much more efficient than recursive

Edge Cases

n = 0

Returns 0 immediately as base case

DSA Rust

if n == 0 { return 0; }

n = 1

Returns 1 immediately as base case

DSA Rust

else if n == 1 { return 1; }

When to Use This Pattern

When you see a problem asking for Fibonacci numbers or similar sequences, reach for recursion because each value depends on previous ones.

Common Mistakes

Mistake: Forgetting base cases causing infinite recursion
Fix: Add explicit checks for n == 0 and n == 1 to stop recursion

Mistake: Using recursion without memoization causing slow performance
Fix: Use memoization or iterative approach for large n

Summary

Calculates Fibonacci numbers by calling itself with smaller inputs.

Use when you want a simple, clear way to define Fibonacci numbers recursively.

The key is to stop recursion at base cases fib(0) and fib(1).

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