Stack based non-recursive Fibonacci - Go implementation 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 = &amp;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 &gt;= 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 &gt; 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 -&gt; 0", 0 == Fibonacci(0))
    fmt.Println("F1 -&gt; 1", 1 == Fibonacci(1))
    fmt.Println("F2 -&gt; 1", 1 == Fibonacci(2))
    fmt.Println("F3 -&gt; 2", 2 == Fibonacci(3))
    fmt.Println("F4 -&gt; 3", 3 == Fibonacci(4))
    fmt.Println("F5 -&gt; 5", 5 == Fibonacci(5))
    fmt.Println("F6 -&gt; 8", 8 == Fibonacci(6))
    fmt.Println("F7 -&gt; 13", 13 == Fibonacci(7))
    fmt.Println("F8 -&gt; 21", 21 == Fibonacci(8))
    fmt.Println("F9 -&gt; 34", 34 == Fibonacci(9))
    fmt.Println("F20 -&gt; 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
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 &lt; 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