Go Program for Fibonacci Using Recursion

You can write a Go program for Fibonacci using recursion by defining a function like func fibonacci(n int) int that returns n if it is 0 or 1, otherwise returns fibonacci(n-1) + fibonacci(n-2).

Examples

Input0

Output0

Input5

Output5

Input10

Output55

How to Think About It

To find the Fibonacci number at position n, check if n is 0 or 1 and return n directly. Otherwise, calculate the sum of the Fibonacci numbers at positions n-1 and n-2 by calling the function recursively.

Algorithm

1

Get the input number n.

2

If n is 0 or 1, return n as the Fibonacci number.

3

Otherwise, call the function recursively for n-1 and n-2.

4

Add the results of the two recursive calls.

5

Return the sum as the Fibonacci number for n.

Code

go

package main

import "fmt"

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

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

Output

55

Dry Run

Let's trace fibonacci(5) through the code

1

Call fibonacci(5)

Since 5 > 1, call fibonacci(4) + fibonacci(3)

2

Call fibonacci(4)

Since 4 > 1, call fibonacci(3) + fibonacci(2)

3

Call fibonacci(3)

Since 3 > 1, call fibonacci(2) + fibonacci(1)

4

Call fibonacci(2)

Since 2 > 1, call fibonacci(1) + fibonacci(0)

5

Call fibonacci(1) and fibonacci(0)

Return 1 and 0 respectively

6

Calculate fibonacci(2)

1 + 0 = 1

7

Calculate fibonacci(3)

fibonacci(2) + fibonacci(1) = 1 + 1 = 2

8

Calculate fibonacci(4)

fibonacci(3) + fibonacci(2) = 2 + 1 = 3

9

Calculate fibonacci(5)

fibonacci(4) + fibonacci(3) = 3 + 2 = 5

Call	Returned Value
fibonacci(1)	1
fibonacci(0)	0
fibonacci(2)	1
fibonacci(3)	2
fibonacci(4)	3
fibonacci(5)	5

Why This Works

Step 1: Base Case

The function returns n directly when n is 0 or 1 to stop recursion.

Step 2: Recursive Calls

For other values, the function calls itself twice with n-1 and n-2 to build the Fibonacci sequence.

Step 3: Summation

The results of the two recursive calls are added to get the Fibonacci number at position n.

Alternative Approaches

Iterative approach

go

package main

import "fmt"

func fibonacciIter(n int) int {
    if n <= 1 {
        return n
    }
    a, b := 0, 1
    for i := 2; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

func main() {
    fmt.Println(fibonacciIter(10))
}

This method uses a loop and is faster and uses less memory than recursion.

Memoization (recursion with caching)

go

package main

import "fmt"

var memo = map[int]int{}

func fibonacciMemo(n int) int {
    if n <= 1 {
        return n
    }
    if val, ok := memo[n]; ok {
        return val
    }
    memo[n] = fibonacciMemo(n-1) + fibonacciMemo(n-2)
    return memo[n]
}

func main() {
    fmt.Println(fibonacciMemo(10))
}

This method stores results to avoid repeated calculations, improving performance.

Complexity: O(2^n) time, O(n) space

Time Complexity

The recursive approach calls itself twice for each non-base case, leading to exponential time O(2^n).

Space Complexity

The maximum depth of the recursion stack is n, so space complexity is O(n).

Which Approach is Fastest?

Iterative and memoized recursion approaches run in O(n) time and are much faster than plain recursion.

Approach	Time	Space	Best For
Recursive (plain)	O(2^n)	O(n)	Simple code, small n
Iterative	O(n)	O(1)	Performance and memory efficiency
Memoization	O(n)	O(n)	Recursive style with better speed