Poor mans tail-call optimization for go

main.go

package main

import (
        "fmt"
        "time"
)

func fib_iter(n int) int {
        current := 0
        prev := 1

        for i := 0; i < n; i++ {
                oldCurrent := current
                current = current + prev
                prev = oldCurrent
        }

        return current
}

func fib_rec(n int) int {
        if n <= 1 {
                return n
        }

        return fib_rec(n-1) + fib_rec(n-2)
}

type Node struct {
        Original int
        Value    int
        Func     func(...int) int
        Args     []int
}

func Add(args ...int) int {
        var out int
        
        for _, v := range args {
                out += v
        }
 
        return out
}

func fib(n int) Node {
        if n <= 1 {
                return Node{Value: n}
        }

        return Node{
                Original: n,
                Func:     Add,
                Args:     []int{n - 1, n - 2},
                Value:    -1,
        }
}

func fib_rec_new(f func(int) Node, n int) int {
        cache := make(map[int]int)
        stack := make([]Node, 0, 1)
        stack = append(stack, f(n))

        for {
                current := stack[len(stack)-1]
                if current.Value == -1 {
                        for _, arg := range current.Args {
                                if v, ok := cache[arg]; ok {
                                        stack = append(stack, Node{Value: v})
                                } else {
                                        stack = append(stack, f(arg))
                                }
                        }
                        continue
                }

                if len(stack) <= 1 {
                        break
                }

                previous := stack[len(stack)-2]
                if previous.Value == -1 {
                        stack[len(stack)-2] = current
                        stack[len(stack)-1] = previous
                        continue
                }

                parent := stack[len(stack)-3]
                parent.Value = parent.Func(current.Value, previous.Value)
                stack[len(stack)-3] = parent
                stack = stack[:len(stack)-2]

                if _, ok := cache[parent.Original]; !ok {
                cache[parent.Original] = parent.Value
                }
        }

        return stack[0].Value
}

func main() {
        var start time.Time
        n := int(25)

        for i := 0; i < 5; i++ {
                start = time.Now()
                fmt.Println("Recursive:", fib_rec(n), "Time:", time.Since(start))
                start = time.Now()
                fmt.Println("Iterative:", fib_iter(n), "Time:", time.Since(start))
                start = time.Now()
                fmt.Println("weirdstuf:", fib_rec_new(fib, n), "Time:", time.Since(start))
                fmt.Println()
        }
}

For n = 50

❯ go run main.go
Recursive: 12586269025 Time: 3m19.798547965s
Iterative: 12586269025 Time: 341ns
weirdstuf: 12586269025 Time: 111.675µs