Fibonacci Using Recursion in DSA Go

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 to reach steps 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: fib(n) needs fib(n-1) and fib(n-2) to compute

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

fib(4) -> fib(3) -> fib(2), fib(1); fib(2)

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

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

fib(4) -> fib(3) -> fib(2) -> fib(1), fib(0); fib(1); fib(2)

Why: fib(2) breaks down further to base cases

Step 4: fib(1) and fib(0) return 1 and 0 respectively

fib(1) = 1, fib(0) = 0

Why: Base cases stop recursion and return known values

Step 5: fib(2) returns 1 + 0 = 1

fib(2) = 1

Why: Sum of fib(1) and fib(0) gives fib(2)

Step 6: fib(1) returns 1

fib(1) = 1

Why: Base case returns 1

Step 7: fib(3) returns fib(2) + fib(1) = 1 + 1 = 2

fib(3) = 2

Why: Sum of fib(2) and fib(1) gives fib(3)

Step 8: fib(2) returns 1

fib(2) = 1

Why: fib(2) base calculation reused

Step 9: fib(4) returns fib(3) + fib(2) = 2 + 1 = 3

fib(4) = 3

Why: Sum of fib(3) and fib(2) gives fib(4)

Result:

fib(4) = 3

Annotated Code

DSA Go

package main

import "fmt"

// fib returns the nth Fibonacci number using recursion
func fib(n int) int {
    if n == 0 {
        return 0 // base case: fib(0) = 0
    }
    if n == 1 {
        return 1 // base case: fib(1) = 1
    }
    return fib(n-1) + fib(n-2) // recursive call
}

func main() {
    n := 4
    result := fib(n)
    fmt.Printf("fib(%d) = %d\n", n, result)
}

if n == 0 { return 0 }

return 0 for base case fib(0)

if n == 1 { return 1 }

return 1 for base case fib(1)

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

sum results of fib(n-1) and fib(n-2) recursively

Output

fib(4) = 3

Complexity Analysis

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

Space: O(n) due to call stack depth from recursion up to n

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

Edge Cases

n = 0

Returns 0 immediately as base case

DSA Go

if n == 0 { return 0 }

n = 1

Returns 1 immediately as base case

DSA Go

if n == 1 { return 1 }

large n (e.g., 40)

Very slow due to exponential calls, may cause stack overflow

DSA Go

No guard; recursion depth and repeated calls cause inefficiency

When to Use This Pattern

When a problem asks for Fibonacci numbers or similar sequences, recursion is a natural pattern to try because each value depends on previous ones.

Common Mistakes

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

Mistake: Calling fib(n-1) and fib(n-2) without return causes no result
Fix: Return the sum of fib(n-1) and fib(n-2) to propagate results

Summary

Calculates Fibonacci numbers by calling itself with smaller inputs.

Use when you want a simple, clear way to find Fibonacci numbers for small n.

The key is that fib(n) depends on fib(n-1) and fib(n-2), so recursion naturally fits.

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