Comparing the speed of calculating the nth Fibonacci number: Recursive, recursive TCO, single loop.

fib.odin

package fib

// odin run fib.odin -file
// odin run fib.odin -file -o:speed
// odin run fib.odin -file -o:aggressive

import "core:fmt"
import "core:time"

print :: fmt.println

main :: proc() {
	FIB_N :: 42 // 30 42 186

	run_fib :: proc(fib_proc: proc(n: u128) -> u128, n: u128) {
		sw := time.Stopwatch{}

		time.stopwatch_start(&sw)
		result := fib_proc(n)
		time.stopwatch_stop(&sw)

		hour, min, sec, nanos := time.precise_clock_from_duration(time.stopwatch_duration(sw))
		fmt.println("h:", hour, ":m:", min, ":s:", sec, ":ns:", nanos, sep = "")
		fmt.println(result)
	}

	/* Recursive */
	run_fib(fib_recursive, FIB_N) // It is recommended to comment out this line when FIB_N is greater than 42

	/* Recursive TCO */
	run_fib(fib_recursive_tco, FIB_N)

	/* Single loop */
	run_fib(fib, FIB_N)
}

fib_recursive :: proc(n: u128) -> u128 {
	switch n {
	case 0, 1:
		return n
	case:
		return fib_recursive(n - 1) + fib_recursive(n - 2)
	}
}

fib_recursive_tco :: proc(n: u128) -> u128 {
	fib_tco_help :: proc(n: u128, acc: u128, prev: u128) -> u128 {
		// fmt.println("n:", n, "acc:", acc, "prev:", prev)
		if n == 0 do return acc
		return fib_tco_help(n = n - 1, acc = prev + acc, prev = acc)
	}
	return fib_tco_help(n = n, acc = 0, prev = 1)
}

fib :: proc(n: u128) -> u128 {
	acc: u128 = 0
	prev: u128 = 1
	for i in 0 ..< n {
		tmp_acc := acc
		acc += prev
		prev = tmp_acc
		// fmt.println("n:", i + 1, "acc:", acc, "prev:", prev)
	}
	return acc
}