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.

score 90 · Accepted Answer · edited Jun 16 '20 at 04:51

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.

score 9 · Answer 2 · answered Jul 20 '20 at 08:11

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

score 8 · Answer 3 · answered Aug 24 '18 at 04:21

8

Another approach

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

The Go Playground

answered Aug 24 '18 at 04:21

jwoodall

81
1
1

score 5 · Answer 4 · answered Aug 25 '14 at 17:50

5

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

answered Aug 25 '14 at 17:50

Stephen Weinberg

51,320
14
134
113

score 4 · Answer 5 · answered Apr 12 '21 at 10:31

4

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

answered Apr 12 '21 at 10:31

king.reflex

313
4
10

score 3 · Answer 6 · answered Feb 21 '20 at 16:53

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

gopadawan · Answer 7 · 2019-01-06T21:45:50.600

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

score 1 · Answer 8 · answered Sep 09 '19 at 03:48

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

score 0 · Answer 9 · answered Nov 30 '18 at 11:57

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

score 0 · Answer 10 · answered Apr 07 '22 at 11:57

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

score 0 · Answer 11 · answered Jan 30 '23 at 14:06

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

score 0 · Answer 12 · answered Mar 15 '23 at 11:41

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

score 0 · Answer 13 · answered Jul 31 '23 at 04:23

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

score -1 · Answer 14 · answered Nov 19 '15 at 12:02

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

Fibonacci closure in go

14 Answers14