Fibonacci closure in go

A small trick

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
    a := 0
    b := 1
    return func() int {
        a, b = b, a+b
        return b-a
    }
}

func main() {
    f := fibonacci()
    for i := 0; i < 10; i++ {
        fmt.Println(f())
    }
}

My favorite clean way to implement iterating through the Fibonacci numbers is to use first as fi - 1, and second as fi. The Fibonacci equation states that:

fi + 1 = fi + fi - 1

Except when we write this in code, in the next round we're incrementing i. So we're effectively doing:

fnext i = fcurrent i + fcurrent i - 1

and

fnext i - 1 = fcurrent i

The way I like to implement this in code is:

first, second = second, first + second

The first = second part corresponds to updating fnext i - 1 = fcurrent i, and the second = first + second part corresponds to updating fnext i = fcurrent i + fcurrent i - 1.

Then all we have left to do is return the old value of first, so we'll store it in a temp variable out of the way before doing the update. In total, we get:

// fibonacci returns a function that returns
// successive fibonacci numbers from each
// successive call
func fibonacci() func() int {
    first, second := 0, 1
    return func() int {
        ret := first
        first, second = second, first+second
        return ret
    }
}

See it in action on the Go Playground.


Another approach

func fibonacci() func() int {
    n1, n := -1, 1
    return func() int {
        n1, n = n, n1+n
        return n
    }
}

The Go Playground