# 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 = &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

• .(int) "conversion" is the type assertions.
– user110702
Commented Oct 7, 2016 at 9:56

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:]
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

• Indeed, makes more sense a linear sequence of Dequeue, Peek then Enqueue the result. I wanted a two element sequence just to exercise types in Go. I didn't give much thought at the access order. I'm accepting your answer since it points the mistake with the chosen data structure and the slice usage. I guess an extra auxiliary variable would replace the slice too. Commented Oct 7, 2016 at 12:08

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