Stack based non-recursive Fibonacci - Go implementation

Question

The following function computes a the last element in a Fibonacci sequence in Go language.

package main

import (
    "fmt"
)

type Element struct {
    Next  *Element
    Value interface{}
}
type Stack struct {
    Top   *Element
    Count int
}

func (stack *Stack) Push(value interface{}) {
    el := Element{
        Value: value,
        Next:  stack.Top,
    }
    stack.Top = &el
    stack.Count++
}
func (stack *Stack) Peek() (value interface{}) {
    if stack.Top != nil {
        value = stack.Top.Value
    }
    return
}
func (stack *Stack) Pop() (value interface{}) {
    if stack.Top != nil {
        value = stack.Top.Value
        stack.Top = stack.Top.Next
        stack.Count--
    }
    return
}
func (stack *Stack) Size() int {
    return stack.Count
}

func Fibonacci(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }

    //for n >= 2 the initial stack has the 0 and 1 values
    stack := Stack{}
    stack.Push(0)
    stack.Push(1)

    // loop from n to 2
    for n > 1 {
        //pop two top elements from stack
        term1 := stack.Pop().(int)
        term2 := stack.Pop().(int)

        //push back the first popped element, this will become term2 on the next iteration
        stack.Push(term1)

        //push the sum of the two elements, this will be the Top element on the next iteration
        stack.Push(term1 + term2)

        //move to the next iteration
        n--

    }

    //the top element in stack represents the last element in the Fibonacci sequence for a given n position
    return stack.Pop().(int)
}
func FibonacciTest() {
    fmt.Println("F0 -> 0", 0 == Fibonacci(0))
    fmt.Println("F1 -> 1", 1 == Fibonacci(1))
    fmt.Println("F2 -> 1", 1 == Fibonacci(2))
    fmt.Println("F3 -> 2", 2 == Fibonacci(3))
    fmt.Println("F4 -> 3", 3 == Fibonacci(4))
    fmt.Println("F5 -> 5", 5 == Fibonacci(5))
    fmt.Println("F6 -> 8", 8 == Fibonacci(6))
    fmt.Println("F7 -> 13", 13 == Fibonacci(7))
    fmt.Println("F8 -> 21", 21 == Fibonacci(8))
    fmt.Println("F9 -> 34", 34 == Fibonacci(9))
    fmt.Println("F20 -> 6765", 6765== Fibonacci(20))
}
func main() {
    FibonacciTest()

}

I'm new to Go language. I'm interested if this code can be improved or what I can add to be more like a Go style. I'm not very sure about the .(int) "conversion" and any explanation will be appreciated.

https://play.golang.org/p/q57CvDaqRV

Answer 1

I'm not convinced that the mechanism of using a stack is a good one. Why did you choose that data structure? In Go, a slice would be a much more appropriate structure, and also probably a lot more memory efficient. What you are looking for is a 2-element queue, not a 2-member stack.

The need for you to pop() term1 and then push it back again, is an indication that the stack is the wrong structure.

Consider a much simpler Fibonacci method, that does essentially the same logic as your method, but .... simpler.

func Fibonacci(n int) int {
    // seed the sequence with the next 2 numbers in the sequence
    fib := []int{0, 1}

    // advance the future 2 sequences as necessary.
    for i := 0; i < n; i++ {
        current := fib[0]
        next := fib[1]
        // remove the first member
        fib = fib[1:]
        // add the next member
        fib = append(fib, current+next)
    }

    return fib[0]
}

This uses a Go slice as a queue, shifting the value from the front of the queue, and adding another value to the end of the queue.

A trick is computing the two values "ahead" instead of the two values "before" the "current" item. This allows you to have simpler logic for the first and second results (but at the expense of calculating a single value you will never use).

See this running in the playground

Answer 2

Look good for me. Can add only 2 remarks:

1.Since as Fibonacci numbers only for non-negative numbers, use uint istead int. Then get:

func Fibonacci(n uint) uint {
    if n < 2 {
        return n
    }

2.Can remove unnecessary push and pop for first iteration if add condition and range variable:

for i := n; i > 1; i-- {
    var term1, term2 uint
    //pop two top elements from stack
    if i == n {
        term1 = 1
        term2 = 0
    } else {
        term1 = stack.Pop().(uint)
        term2 = stack.Pop().(uint)
    }

As result: https://play.golang.org/p/zMgX-YzA7Z