3 ms·
some compilers can rearrange it to be tail recursive automatically
by gameswithgo 8y ago
some compilers can rearrange it to be tail recursive automatically
- SeanLuke 8y agoWhich compilers can rearrange fib, with two recursive calls, into being tail recursive?
- FeepingCreature 8y agoIf it knows it's a pure function, it's possible. It'd have to be a very specific optimization pass though.
- jcranmer 8y agoAny LLVM-based compiler. GCC.
- Jtsummers 8y agoPretend you're a compiler, what changes would you make to this to make it tail recursive: fib(0) -> 1; fib(1) -> 1; fib(N) -> fib(N-1) + fib(N-2). Rules: Making a second function (fib_help) is permitted. Shouldn't use any more memory than this one uses.
- FeepingCreature 8y agoFun challenge. https://paste.pound-python.org/show/m403qNkpS5I8dnYjJGJq/ https://paste.pound-python.org/show/m403qNkpS5I8dnYjJGJq/ I wanna see the compiler that gets that.
- DonaldPShimoda 8y agoBut that doesn't make it "poster boy" material, in my opinion.
- rothron 8y agoI called it that because I've seen fib be the go-to example of so many introductions to functional programming. But I suppose it's more accurate to describe it as the poster boy example for changing an implementation to make it tail recurse.