fib.go

package main

import (
	"fmt"
)

// Calculate fib sequence
// This is done linerally as recursive calculation is an exponential explosion
// in time, and after the around 35th digit or so would be unreasonable to calculate
//
// https://en.wikipedia.org/wiki/Fibonacci_number
//
func fib(n int) uint64 {

	// make the list
	seq := make([]uint64, n+1, n+2)

	// edge case < 2, create the space for 0 and 1
	if n < 2 {
		seq = seq[0:2]
	}

	// Manually set n-1, and n-2
	seq[0] = 0
	seq[1] = 1

	// f(n) = f(n-1) + f(n-2)
	for i := 2; i <= n; i++ {
		seq[i] = seq[i-1] + seq[i-2]
	}
	return seq[n]
}

// Recursive calculation - This could take a very long time (see above)
//
func fibRecurse(n int) uint64 {

	// Edge case 0
	if n <= 0 {
		return 0
	}

	// Edge case 1
	if n == 1 {
		return 1
	}

	// Recurse to calculate
	// f(n) = f(n-1) + f(n-2)
	return fibRecurse(n-1) + fibRecurse(n-2)
}

//	Get the digit of the fib sequence that the user wants to calculate to
//
func getNth() int {

	complete := false
	destInt := 0

	for !complete {

		fmt.Print("Enter the \"nth\" digit to calculate to: ")
		fmt.Scan(&destInt)

		if destInt < 0 {

			fmt.Println("Number must be greater than or equal to 0 !")
		} else {

			complete = true
		}
	}

	return destInt
}

//	Entry point
//
func main() {

	// Get the 'nth' number that they want to calculate to
	destInt := getNth()

	// Calculate the number offset by 1 as the fib function 0-indexes
	for i := 0; i <= destInt-1; i++ {

		// Print number and space
		fmt.Print(fib(i))

		// Uncomment to see how slow fibRecurse is
		//
		//fmt.Print(fibRecurse(i))

		fmt.Print(" ")
	}
	fmt.Println("")
}