goclosuresfibonacci

Fibonacci closure in go


I am following the go tour on their official website and I have been asked to write a Fibonacci generator. Here it is:

 package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
    first := 0
    second := 0
    return func() int{
        if(first == 0) {
         first = 1
         second = 1
         return 0
        }else {
            current := first   
            firstc := second
            second = first + second
            first = firstc
            return current
        }



    }
}

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

It works. However I consider it very ugly and I'm sure there has to be a better solution. I have been thinking about posting this on the code-review however since I'm asking for a better approach I thought this is the right place to post it.

Is there a better way to write this code?

Here is the task:

Implement a fibonacci function that returns a function (a closure) that returns successive fibonacci numbers.


Solution

  • 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.