Fibonacci Using Recursion in DSA Rust - Execution Trace

Concept Flow - Fibonacci Using Recursion

Call fibonacci(n)

↓

Is n <= 1?

Yes→Return n

No↓

Call fibonacci(n-1)

↓

Call fibonacci(n-2)

↓

Add results of fibonacci(n-1) + fibonacci(n-2)

↓

Return sum

↓

End call for fibonacci(n)

The function calls itself with smaller values until it reaches base cases n=0 or n=1, then returns and sums results back up.

Execution Sample

DSA Rust

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

println!("{}", fibonacci(4));

Calculates the 4th Fibonacci number by recursively summing the two previous Fibonacci numbers.

Execution Table

Step	Call	Arguments	Return Value	Stack Depth	Action
1	fibonacci	4	-	1	Check if 4 <= 1 (No), call fibonacci(3) and fibonacci(2)
2	fibonacci	3	-	2	Check if 3 <= 1 (No), call fibonacci(2) and fibonacci(1)
3	fibonacci	2	-	3	Check if 2 <= 1 (No), call fibonacci(1) and fibonacci(0)
4	fibonacci	1	1	4	Base case n=1, return 1
5	fibonacci	0	0	4	Base case n=0, return 0
6	fibonacci	2	1	3	Return 1 + 0 = 1
7	fibonacci	1	1	3	Base case n=1, return 1
8	fibonacci	3	2	2	Return 1 + 1 = 2
9	fibonacci	2	-	2	Check if 2 <= 1 (No), call fibonacci(1) and fibonacci(0)
10	fibonacci	1	1	3	Base case n=1, return 1
11	fibonacci	0	0	3	Base case n=0, return 0
12	fibonacci	2	1	2	Return 1 + 0 = 1
13	fibonacci	4	3	1	Return 2 + 1 = 3
14	-	-	-	-	End of recursion, final result 3

💡 Recursion ends when all calls reach base cases n=0 or n=1 and return values.

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 10	After Step 11	After Step 12	Final
n	4	1	0	2	1	3	1	0	2	4
Return Value	-	1	0	1	1	2	1	0	1	3
Stack Depth	1	4	4	3	3	2	3	3	2	1

Key Moments - 3 Insights

Why does fibonacci(2) get called multiple times?

Because the function calls fibonacci(n-1) and fibonacci(n-2) separately each time, causing repeated calls as shown in steps 3, 6, 9, and 12.

When does the recursion stop?

Recursion stops at base cases when n is 0 or 1, returning immediately as shown in steps 4, 5, 7, 10, and 11.

Why is the stack depth highest at step 4?

Because the function calls keep nesting deeper until base cases are reached, increasing stack depth as shown in the variable_tracker and execution_table.

Visual Quiz - 3 Questions

Look at the execution table, what is the return value of fibonacci(3) at step 8?

A 1

B 3

C 2

D 0

💡 Hint

Check the 'Return Value' column at step 8 in the execution_table.

At which step does the recursion first reach the base case n=0?

A Step 5

B Step 10

C Step 4

D Step 11

💡 Hint

Look for the first step where 'Arguments' is 0 and 'Return Value' is 0.

If we call fibonacci(5) instead of fibonacci(4), how would the stack depth change at the first call?

A It would stay the same

B It would increase by 1

C It would decrease by 1

D It would double

💡 Hint

Consider that fibonacci(5) calls fibonacci(4) and fibonacci(3), increasing recursion depth by one.

Concept Snapshot

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

- Base cases: n=0 or n=1 return n
- Recursive calls reduce n until base
- Results sum back up to final answer

Full Transcript

This visualization traces the recursive Fibonacci function in Rust. The function calls itself with smaller numbers until reaching base cases n=0 or n=1, which return immediately. Each call waits for the results of fibonacci(n-1) and fibonacci(n-2), then sums them. The execution table shows each call's arguments, return values, and stack depth. The variable tracker follows n, return values, and stack depth changes. Key moments clarify why calls repeat, when recursion stops, and stack depth behavior. The quiz tests understanding of return values, base cases, and recursion depth changes. The snapshot summarizes the function structure and recursion rules.

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