Go Golang - recursive function, fibonacci sequence

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))
}

try it for fib(100)

@d4rk5eed it just breaks after 90

�⚡ ./fib2
0 0
10 55
20 6765
30 832040
40 1.02334154e+08
50 1.2586269024e+10
60 1.548008755919e+12
70 1.90392490709134e+14
80 2.3416728348467676e+16
90 2.8800671943708155e+18
100 3.542248481792618e+20
110 4.356677625885483e+22
120 5.358359254990965e+24
130 6.590346215876297e+26
140 8.105590009602348e+28
150 9.969216677189299e+30
160 1.2261325953941875e+33
170 1.5080434001680788e+35
180 1.8547707689471975e+37
190 2.2812172414650363e+39
200 2.8057117299250997e+41
210 3.4507973060837266e+43
220 4.244200115309991e+45
230 5.22002106210068e+47
240 6.420201486372305e+49
250 7.896325826131725e+51
260 9.711838745993384e+53
270 1.194477202498925e+56
280 1.4691098406862176e+58
290 1.8068856563237978e+60
300 2.222322446294202e+62
310 2.733275920376237e+64
320 3.3617071498181414e+66
330 4.134626466684276e+68
340 5.085254383306678e+70
350 6.2544494288205456e+72
360 7.692464272010941e+74
370 9.461105609630573e+76
380 1.1636390653418405e+79
390 1.4311814393143676e+81
400 1.7602368064501377e+83
410 2.1649481537897377e+85
420 2.6627102054807328e+87
430 3.274917057925922e+89
440 4.027881710228336e+91
450 4.95396701187506e+93
460 6.092976636435301e+95
470 7.493865866114232e+97
480 9.216845717656862e+99
490 1.1335970846131328e+102

Profiled using : https://blog.golang.org/profiling-go-programs

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)
}

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)
}

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))
	}

}

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

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))
}

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]
}```