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.

Bifilar

Answer 1

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.

Superannuated

Answer 2

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

Licorice

Answer 3

Another approach

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

The Go Playground

Ephesians

Answer 4

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

Wivina

Answer 5

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

Effervescent

Answer 6

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

Owings

Answer 7

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

Snuggle

Answer 8

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

Kerbstone

Answer 9

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

Hengel

Answer 10

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

Unstoppable

Answer 11

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

Goosegog

Answer 12

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

Aureus

Answer 13

I was able to implement a recursive closure solution using hints from this post on the correct recursive syntax in go: https://mcmap.net/q/540135/-how-to-recurse-a-closure-in-go-duplicate

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

Morphology

Answer 14

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

Geier

Thank you for your interest in contributing to the Stack Overflow community. This question already has quite a few answers—including one that has been extensively validated by the community. Are you certain your approach hasn’t been given previously? If so, it would be useful to explain how your approach is different, under what circumstances your approach might be preferred, and/or why you think the previous answers aren’t sufficient. Can you kindly edit your answer to offer an explanation? – Etymon

Looks a lot like this answer. It even seems to do the same thing. Does this offer some significant advantage? – Darcie

Answer 15

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

Cyclometer

Answer 16

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
}

Dijon

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Dragnet