Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save shockalotti/d29021387e8bb3875d28 to your computer and use it in GitHub Desktop.
Save shockalotti/d29021387e8bb3875d28 to your computer and use it in GitHub Desktop.
Go Golang - recursive function, fibonacci sequence
package main
import "fmt"
func fib(n uint) uint {
if n == 0 {
return 0
} else if n == 1 {
return 1
} else {
return fib(n-1) + fib(n-2)
}
}
func main() {
n := uint(10)
fmt.Println(fib(n))
}
Copy link

ghost commented Oct 30, 2016

import (
        "fmt"
)

func main() {
        var x = fib(10)
        fmt.Println(x)
}

func fib(number int) int {
  if number == 0 || number == 1{
        return number
  }

  return fib(number - 2) + fib(number - 1)
}

@danielrangelmoreira
Copy link

danielrangelmoreira commented Apr 18, 2017

Linear O(n) implementation as seen in Youtube Video Lecture

3736710778780434371
./fibonacci 0,00s user 0,00s system 48% cpu 0,009 total

package main

func fib(n int) int {
	fn := make(map[int]int)
	for i := 0; i <= n; i++ {
		var f int
		if i <= 2 {
			f = 1
		} else {
			f = fn[i-1] + fn[i-2]
		}
		fn[i] = f
	}
	return fn[n]
}

func main() {
	var x = fib(100)
	println(x)
}

@danielrangelmoreira
Copy link

Another linear implementation using math/big package for very large integers still blazing fast. try with 20000 or bigger ;)

package main

import (
	"fmt"
	"math/big"
	"os"
	"strconv"
)

func fib(n int) *big.Int {
	fn := make(map[int]*big.Int)

	for i := 0; i <= n; i++ {
		var f = big.NewInt(0)
		if i <= 2 {
			f.SetUint64(1)
		} else {
			f = f.Add(fn[i-1], fn[i-2])
		}
		fn[i] = f
	}
	return fn[n]
}

func main() {
	for _, s := range os.Args[1:] {
		n, e := strconv.Atoi(s)
		if e != nil {
			panic(e)
		}
		fmt.Printf("%s\n", fib(n))
	}

}

@msh2050
Copy link

msh2050 commented May 12, 2017

converted from python science book this method is much faster...

package main

import (
	"fmt"
	"math/big"
	"time"
)

func fib(n int) *big.Int {
	fn := make(map[int]*big.Int)

	for i := 0; i <= n; i++ {
		var f = big.NewInt(0)
		if i <= 2 {
			f.SetUint64(1)
		} else {
			f = f.Add(fn[i-1], fn[i-2])
		}
		fn[i] = f

	}
	return fn[n]
}

func fib2(n int) *big.Int {
	// Initialize two big ints with the first two numbers in the sequence.
	a := big.NewInt(0)
	b := big.NewInt(1)

	// Loop while a is smaller than 1e100.
	for i := 0; i <= n; i++ {
		a.Add(a, b)
		a, b = b, a
	}
	return a
}

func main() {
	start1 := time.Now()
	for i := 0; i <= 10000; i++ {
		fmt.Printf("Fin(%d) is %d \n", i, fib(i))
	}
	elapsed1 := time.Since(start1)
	start2 := time.Now()
	for i := 0; i <= 10000; i++ {
		fmt.Printf("Fin(%d) is %d \n", i, fib2(i))
	}
	elapsed2 := time.Since(start2)
	fmt.Printf("time eclibaced1 is %s \n", elapsed1)
	fmt.Printf("time eclibaced2 is %s \n", elapsed2)

}

on my PC
time eclibaced1 is 37.3392202s
time eclibaced2 is 4.795402s

@vchakoshy
Copy link

package main

func fib(n int) int {
	// 0 1 1 2 3 5 8 13 21
	f := make([]int, n+1)
	f[0] = 0
	if n > 0 {
		f[1] = 1
		for i := 2; i <= n; i++ {
			f[i] = f[i-1] + f[i-2]
		}
	}

	return f[n]
}

func main() {
	print(fib(100))
}

@mygedz
Copy link

mygedz commented Feb 27, 2024

package main

import "fmt"

func main() {
	var num1 int
	fmt.Scan(&num1)

	fmt.Println(fibonacci(num1))
}

func fibonacci(n int) int {
	fib := make([]int, n+1)
	fib[0], fib[1] = 0, 1
	for i := 2; i <= n; i++ {
		fib[i] = fib[i-1] + fib[i-2]
	}
	return fib[n]
}```

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment