Fibonacci closure in go

Question

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.

Answer 1

• Try it out in the go playground: https://go.dev/play/p/W95Iqofia4I
• Wikipedia Entry: https://en.wikipedia.org/wiki/Fibonacci_sequence
• Full code: https://gist.github.com/benkoshy/ab0471e1c73152a1dc7f3e9b0430a8df

package main

import "fmt"

func fibonacci() func() int {
    n_minus_2, n_minus_1 := 0, 1

    current := 0

    return func() int {
        current = n_minus_2 + n_minus_1 // calculate current "fibonacci" number

        // update previous numbers
        // do this after calculating the current number
        n_minus_2, n_minus_1 = n_minus_1, current        

        return current       
    }

}

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

// This implementation starts at 1
// Returns:
// 1
// 2
// 3
// 5
// 8
// 13
// 21
// 34
// 55
// 89

Answer 2

func fibonacci() func() int {
    first := 0
    second := 0
    return func() int {

        if first == 0 {
            first = 1
            second = 1
            return 0
        } else {
            current := first
            first = second
            second = second + current
            return current
        }
    }
}

Answer 3

func fibonacci() func() int {
    left, right := 0, 1
    return func() int {
        left, right = right, left+right
        return right-left
    }
}

Answer 4

package main

import (
    "fmt"
    "time"
)

var (
    a     int = 1
    b     int = 2
    start time.Time
)

func main() {
    // fmt.Printf("New %v %v \n", a, b)
    if start.IsZero() == true {
        start = time.Now()
    }

    defer recoverMain()
    fmt.Println(a)
    if b > 1000000 {
        sub := time.Since(start)
        fmt.Printf("work time  %v \n", sub.Microseconds())
        return
    }
    a, b = b, a+b
    panic("start")
}

func recoverMain() {
    if r := recover(); r != nil {
        main()
    }
    // return
}

Answer 5

I was able to implement a recursive closure solution using hints from this post on the correct recursive syntax in go: https://stackoverflow.com/a/34194763/1592607

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func(int) int {
  var recur func(int) int
  recur = func(x int) int {
    switch x {
      case 0:
        return 0
      case 1:
        return 1
      default:
        return (recur(x - 1) + recur(x - 2))
    }
  }
  return recur
}

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

Answer 6

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
    r := []int{0,0,1}
    return func() int{
        r = []int{r[1],r[2],r[1]+r[2]}
        return r[0]
    }
}

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

Answer 7

Try this solution if you want that your answer start with zero.

func fibonacci() func() int {
    a, b := 0, 1
    upd := func() { a, b = b, a+b }
    return func() int {
        defer upd()
        return a
    }
}

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

Answer 8

I had a bit of trouble with this exercise as well, thank you to everyone for these answers. Thought I would also share that if you continue the go tour and make it to the concurrency section, there is another way to implement this using channels in concurrency lesson 4.

Code snippet from lesson 4:

package main

import (
    "fmt"
)

func fibonacci(n int, c chan int) {
    x, y := 0, 1
    for i := 0; i < n; i++ {
        c <- x
        x, y = y, x+y
    }
    close(c)
}

func main() {
    c := make(chan int, 10)
    go fibonacci(cap(c), c)
    for i := range c {
        fmt.Println(i)
    }
}

Answer 9

This is how I have done.

func fibonacci() func() int {
     var s = []int{0,1}

     return func() int{
                ret := s[0]
                s[0],s[1] = s[1],s[0]+s[1]
                return ret
            }
}

Answer 10

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())
    }
}

Answer 11

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

f_{i + 1} = f_i + f_{i - 1}

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

f_{next i} = f_{current i} + f_{current i - 1}

and

f_{next i - 1} = f_{current i}

The way I like to implement this in code is:

first, second = second, first + second

The first = second part corresponds to updating f_{next i - 1} = f_{current i}, and the second = first + second part corresponds to updating f_{next i} = f_{current i} + f_{current 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.

Answer 12

Here is also my suggestion by storing each number in a Map.

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,
// 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025,
// 121393, 196418, 317811, 514229
func fibonacci() func() int {
    numbers := make(map[int]int)
    n := 0
    return func() int {
        if n == 0 {
            numbers[n] = 0
            n++
            return 0
        }
        if n == 1 {
            numbers[n] = 1
            n++
            return 1
        }
        number := numbers[n-1] + numbers[n-2]
        numbers[n] = number
        n++
        return number
    }}

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

Answer 13

Or u may use this approach...simple and understandable, though not very different from the previous answers.

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
    f1 := 0
    f2 := 1
    return func() int {
        temp := f1+f2
        temp2 := f1
        f1 = f2
        f2 = temp
        return temp2
    }
}

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

Answer 14

Besides the already provided answers you could also use a defer function for it:

package main

import "fmt"

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

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

Go Playground

But i guess jwoodalls answers is the most performant one.

Edit: But if you wanna use unsigned integers (to show off how many fibonacci numbers you can compute on your architecture ;) ) you would have to use either the approach with the variable holding the return value or the defer function.

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an uint.
func fibonacci() func() uint {
    var secondLast uint
    var last uint = 1
    return func() uint {
        defer func() {
            secondLast, last = last, secondLast + last
        }()
        return secondLast
    }
}

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

Go Playground

EditEdit: Or even better: use float64!!!

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an float64.
func fibonacci() func() float64 {
    var secondLast float64
    var last float64 = 1
    return func() float64 {
        defer func() {
            secondLast, last = last, secondLast+last
        }()
        return secondLast
    }
}

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

Go Playground

Answer 15

package main

import "fmt"

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

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

Answer 16

Another approach

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

The Go Playground

Answer 17

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 second == 0 {
            second = 1
        } else if first == 0 {
            first = 1
        } else {
            first, second = second, first + second
        }
        return second
    }
}

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

Answer 18

I would make use of multiple assignment, reduce the length of identifiers, and remove that if statment:

func fibonacci() func() int {
    var a, b int
    b = 1
    return func() int {
        ret := a
        a, b = b, a+b
        return ret
    }
}