Fibonacci Using Recursion in DSA Rust - Build from Scratch

Fibonacci Using Recursion

📖 Scenario: You are helping a friend understand how to calculate Fibonacci numbers using a simple function that calls itself.The Fibonacci sequence starts with 0 and 1, and each next number is the sum of the two before it.

🎯 Goal: Build a Rust program that uses a recursive function to find the Fibonacci number at a given position.

📋 What You'll Learn

Create a function called fibonacci that takes an usize parameter n and returns a usize.

Use recursion inside the fibonacci function to calculate the Fibonacci number.

Call the fibonacci function with the value 7 and store the result in a variable called result.

Print the value of result.

💡 Why This Matters

🌍 Real World

Fibonacci numbers appear in nature, computer algorithms, and financial models. Understanding recursion helps solve problems that break down into smaller similar problems.

💼 Career

Many programming jobs require understanding recursion and how to implement it efficiently, especially in algorithm design and problem solving.

1

Create the Fibonacci function signature

Write a function called fibonacci that takes a parameter n of type usize and returns a usize. For now, make it return 0.

DSA Rust

fn fibonacci(n: usize) -> usize {
    // Your code here
}

Hint

Start by writing the function header and return 0 inside the function body.

2

Add base cases for recursion

Inside the fibonacci function, add two base cases: if n is 0, return 0; if n is 1, return 1.

DSA Rust

fn fibonacci(n: usize) -> usize {
    // Add base cases for n == 0 and n == 1
    
}

Hint

Use if and else if to check for 0 and 1 and return the correct values.

3

Add recursive call to calculate Fibonacci

In the fibonacci function, after the base cases, return the sum of fibonacci(n - 1) and fibonacci(n - 2).

DSA Rust

fn fibonacci(n: usize) -> usize {
    if n == 0 {
        return 0;
    } else if n == 1 {
        return 1;
    }
    // Your code here
}

Hint

Return the sum of the function called with n - 1 and n - 2.

4

Call the function and print the result

Call the fibonacci function with the value 7 and store the result in a variable called result. Then print result.

DSA Rust

fn fibonacci(n: usize) -> usize {
    if n == 0 {
        return 0;
    } else if n == 1 {
        return 1;
    }
    fibonacci(n - 1) + fibonacci(n - 2)
}

// Your code here

Hint

Use let result = fibonacci(7); and println!("{}", result); inside a main function.

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