Fibonacci Using Recursion in DSA Go - 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

The function calls itself with smaller inputs until it reaches the base case, then returns and sums results back up.

Execution Sample

DSA Go

func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    return fibonacci(n-1) + fibonacci(n-2)
}

This code calculates the nth Fibonacci number by calling itself recursively.

Execution Table

Step	Call Stack (Top)	Current n	Action	Return Value	Stack Depth
1	fibonacci(4)	4	Check if n <= 1 (No), call fibonacci(3)		1
2	fibonacci(3)	3	Check if n <= 1 (No), call fibonacci(2)		2
3	fibonacci(2)	2	Check if n <= 1 (No), call fibonacci(1)		3
4	fibonacci(1)	1	Check if n <= 1 (Yes), return 1	1	4
5	fibonacci(0)	0	Check if n <= 1 (Yes), return 0	0	4
6	fibonacci(2)	2	Sum fibonacci(1)+fibonacci(0) = 1+0	1	3
7	fibonacci(1)	1	Check if n <= 1 (Yes), return 1	1	2
8	fibonacci(3)	3	Sum fibonacci(2)+fibonacci(1) = 1+1	2	2
9	fibonacci(2)	2	Check if n <= 1 (No), call fibonacci(1)		2
10	fibonacci(1)	1	Check if n <= 1 (Yes), return 1	1	3
11	fibonacci(0)	0	Check if n <= 1 (Yes), return 0	0	3
12	fibonacci(2)	2	Sum fibonacci(1)+fibonacci(0) = 1+0	1	2
13	fibonacci(4)	4	Sum fibonacci(3)+fibonacci(2) = 2+1	3	1
14	-	-	All calls complete, final return 3	3	0

💡 All recursive calls resolved, final Fibonacci number for n=4 is 3

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 6	After Step 8	After Step 13	Final
n	4	1	0	2	3	4	4
Return Value		1	0	1	2	3	3
Stack Depth	1	4	4	3	2	1	0

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.

Why do we return n immediately when n <= 1?

This is the base case stopping recursion, as shown in steps 4, 5, 7, 10, and 11, preventing infinite calls.

How does the function combine results from recursive calls?

After both fibonacci(n-1) and fibonacci(n-2) return, their results are added and returned, as seen in steps 6, 8, 12, and 13.

Visual Quiz - 3 Questions

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

A 2

B 1

C 3

D 0

💡 Hint

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

At which step does the recursion reach the base case for fibonacci(0)?

A Step 4

B Step 5

C Step 10

D Step 12

💡 Hint

Look for the step where n=0 and return happens immediately.

If we change the input n from 4 to 3, how many total calls will be made?

A 9

B 5

C 7

D 4

💡 Hint

Count the number of calls for n=4 in the execution_table and consider one less level.

Concept Snapshot

Fibonacci Using Recursion:
- Base case: if n <= 1, return n
- Recursive case: return fibonacci(n-1) + fibonacci(n-2)
- Calls build a call stack until base case
- Results sum back up the stack
- Simple but has repeated calls (inefficient)

Full Transcript

This visualization shows how the recursive Fibonacci function works step-by-step. The function calls itself with smaller numbers until it reaches the base case where n is 0 or 1. At that point, it returns the value immediately. Then the function adds the results of the two smaller calls and returns the sum. The execution table tracks each call, the current value of n, the action taken, and the return value. The variable tracker shows how n, return values, and stack depth change over time. Key moments clarify why base cases stop recursion, why some calls repeat, and how results combine. The quiz tests understanding of return values, base cases, and call counts. This method is clear but inefficient due to repeated calls.

Practice

1. What does the Fibonacci sequence represent when calculated using recursion?

easy

A. Each number is the product of the two preceding numbers

B. Each number is the difference of the two preceding numbers

C. Each number is the sum of the two preceding numbers

D. Each number is the square of the previous number

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 C

4. Quick Check:

   Fibonacci = sum of two previous numbers [OK]

Hint: Remember Fibonacci adds two previous numbers [OK]

Common Mistakes:

• Thinking Fibonacci multiplies previous numbers
• Confusing difference with sum
• Assuming Fibonacci squares previous number

2. Which of the following is the correct Go function signature for a recursive Fibonacci function?

easy

A. func fibonacci(n int) int

B. func fibonacci(n string) string

C. func fibonacci(n float64) float64

D. func fibonacci() int

Solution

1. Step 1: Identify parameter and return types

   The Fibonacci function takes an integer input and returns an integer output.

2. Step 2: Match correct Go syntax

   func fibonacci(n int) int matches the correct signature: func fibonacci(n int) int.

3. Final Answer:

   func fibonacci(n int) int -> Option A

4. Quick Check:

   Input and output are integers [OK]

Hint: Fibonacci uses int input and int output [OK]

Common Mistakes:

• Using string or float types incorrectly
• Omitting function parameters
• Wrong return type

3. What is the output of the following Go code?

func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    return fibonacci(n-1) + fibonacci(n-2)
}

func main() {
    fmt.Println(fibonacci(5))
}

medium

A. 5

B. 8

C. 3

D. 13

Solution

1. Step 1: Trace fibonacci(5) calls

   fibonacci(5) = fibonacci(4) + fibonacci(3), fibonacci(4) = 3, fibonacci(3) = 2, so total = 5.

2. Step 2: Calculate final value

   Sum of fibonacci(4) and fibonacci(3) is 3 + 2 = 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Fibonacci(5) = 5 [OK]

Hint: Recall Fibonacci(5) = 5 from sequence 0,1,1,2,3,5 [OK]

Common Mistakes:

• Confusing index starting at 0 or 1
• Adding wrong recursive results
• Miscounting base cases

4. Identify the error in this recursive Fibonacci function and select the fix:

func fibonacci(n int) int {
    if n == 0 {
        return 0
    } else if n == 1 {
        return 1
    }
    return fibonacci(n-1) - fibonacci(n-2)
}

medium

A. Add a loop instead of recursion

B. Change base case n == 0 to n == 2

C. Remove else if condition

D. Change '-' to '+' in the return statement

Solution

1. Step 1: Check recursive return operation

   The Fibonacci sequence sums previous two numbers, but code subtracts them.

2. Step 2: Correct the operation

   Replace '-' with '+' to correctly add fibonacci(n-1) and fibonacci(n-2).

3. Final Answer:

   Change '-' to '+' in the return statement -> Option D

4. Quick Check:

   Fibonacci sums previous two numbers [OK]

Hint: Fibonacci adds, never subtracts previous two numbers [OK]

Common Mistakes:

• Using subtraction instead of addition
• Changing base cases incorrectly
• Removing necessary conditions

5. How can you optimize the recursive Fibonacci function to avoid repeated calculations?

hard

A. Increase the recursion depth limit

B. Use memoization to store and reuse results

C. Use a global variable to count calls

D. Replace recursion with a random number generator

Solution

1. Step 1: Understand repeated calculations problem

   Recursive Fibonacci recalculates same values many times, causing inefficiency.

2. Step 2: Apply memoization technique

   Memoization stores results of previous calls to reuse them, reducing repeated work.

3. Final Answer:

   Use memoization to store and reuse results -> Option B

4. Quick Check:

   Memoization optimizes recursion by caching [OK]

Hint: Cache results to avoid repeated recursion calls [OK]

Common Mistakes:

• Increasing recursion depth does not fix inefficiency
• Counting calls doesn't optimize calculation
• Random numbers unrelated to Fibonacci