51

Does the Go programming language, as of now, optimize tail calls? If not, does it at least optimize tail-recursive calls of a function to itself?

Rene Knop
  • 1,788
  • 3
  • 15
  • 27
dxuhuang
  • 990
  • 1
  • 9
  • 18
  • 2
    If I follow https://groups.google.com/forum/?fromgroups=#!topic/golang-nuts/iveUW_2--cI, not really – VonC Aug 24 '12 at 04:13
  • You could test it out by writing a tail-recursive function, then writing its iterative equivalent and comparing memory usage. – Snowball Aug 24 '12 at 04:18
  • 3
    Tail call elimination isn't really an optimisation. Since turning it off changes the run-ability of a program. – Jesse Aug 28 '12 at 06:33
  • No they are not going to do it https://github.com/golang/go/issues/22624 – Bhupesh Varshney Jun 04 '20 at 06:57

4 Answers4

19

Everything you can find over the Internet, that "Go supports tailable recursions in some cases", and that was told in mailing list:

It is already there in 6g/8g for certain cases, and in gccgo somewhat more generally.

We do not currently plan to change the language to require that compilers implement tail call optimization in all cases. If you must have a tail call, you use a loop or a goto statement.

To get those cases you'd better dig into golang source, which is open.

ib.
  • 27,830
  • 11
  • 80
  • 100
Rostyslav Dzinko
  • 39,424
  • 5
  • 49
  • 62
  • 3
    You cannot replace all tail calls by loops or gotos. –  Feb 23 '15 at 14:16
  • 1
    @райтфолд: Technically you can, but it would get ugly if you have to rewrite the code to be all in one function. – Matt Mar 13 '15 at 21:57
  • 1
    You can always implement tail calls in code with trampolines, but that requires doing a global rewrite and to write code in a monad pattern which is even harder without generics (though Go is getting them in 2022). – saolof Feb 08 '22 at 18:28
5

I just wrote a new library to deal with this restriction. Thanks to the new generics language feature comes with Go 1.18. Now, type safe stackless mutually recursive functions are possible.

https://github.com/kandu/go_tailcall

ZAN DoYe
  • 51
  • 1
  • 1
  • 2
    Please be sure to read [Stack Overflow's self-promotion policy](https://stackoverflow.com/help/promotion) when referencing your own content. – Jeremy Caney Jul 06 '22 at 01:12
4

Extending @Rostyslav's excellent answer. If you must have a tail call, (in this example a tail recursive call) you can do something like this.

package main

import "fmt"

func tail(i int) {
    if i == 0 {
        return
    } else {
        fmt.Println(i)
        tail(i - 1) //tail recursive call
    }
}
func main() {
    tail(3) //3, 2, 1
}
3

It does not. Nor is there any plan to according to the core development team on the mailing list.

Jeremy Wall
  • 23,907
  • 5
  • 55
  • 73