Questions tagged [tail-call-optimization]
A tail-call optimization is when a function returns directly the result of a called function, to avoid allocating a new stack frame. It is especially useful in recursive functions.
tail-call-optimization
176
questions
1103
votes
10
answers
294k
views
What is tail call optimization?
Very simply, what is tail-call optimization?
More specifically, what are some small code snippets where it could be applied, and where not, with an explanation of why?
- 13.2k
111
votes
3
answers
71k
views
What is the Scala annotation to ensure a tail recursive function is optimized?
I think there is @tailrec annotation to ensure the compiler will optimize a tail recursive function. Do you just put it in front of the declaration? Does it also work if Scala is used in scripting ...
- 41.6k
104
votes
4
answers
32k
views
Does Haskell have tail-recursive optimization?
I discovered the "time" command in unix today and thought I'd use it to check the difference in runtimes between tail-recursive and normal recursive functions in Haskell.
I wrote the following ...
- 1,143
98
votes
5
answers
23k
views
Why does the JVM still not support tail-call optimization?
Two years after does-the-jvm-prevent-tail-call-optimizations, there seems to be a prototype implementation and MLVM has listed the feature as "proto 80%" for some time now.
Is there no active ...
- 28.2k
81
votes
3
answers
4k
views
Why would code actively try to prevent tail-call optimization?
The title of the question might be a bit strange, but the thing is that, as far as I know, there is nothing that speaks against tail call optimization at all. However, while browsing open source ...
- 25.2k
76
votes
2
answers
11k
views
Does Swift implement tail call optimization? and in mutual recursion case?
In particular if I have the following code:
func sum(n: Int, acc: Int) -> Int {
if n == 0 { return acc }
else { return sum(n - 1, acc + n) }
}
Will Swift compiler optimize it to a loop? And ...
- 3,384
64
votes
5
answers
37k
views
How do I replace while loops with a functional programming alternative without tail call optimization?
I am experimenting with a more functional style in my JavaScript; therefore, I have replaced for loops with utility functions such as map and reduce. However, I have not found a functional ...
- 829
53
votes
4
answers
17k
views
Tail Call Optimization in Go
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?
- 1,050
46
votes
5
answers
5k
views
Why won't the Scala compiler apply tail call optimization unless a method is final?
Why won't the Scala compiler apply tail call optimization unless a method is final?
For example, this:
class C {
@tailrec def fact(n: Int, result: Int): Int =
if(n == 0)
...
- 30.3k
38
votes
2
answers
12k
views
What is tail-recursion elimination?
Steve Yegge mentioned it in a blog post and I have no idea what it means, could someone fill me in?
Is it the same thing as tail call optimization?
- 49.1k
37
votes
4
answers
18k
views
Node.js tail-call optimization: possible or not?
I like JavaScript so far, and decided to use Node.js as my engine partly because of this, which claims that Node.js offers TCO. However, when I try to run this (obviously tail-calling) code with Node....
- 3,100
35
votes
8
answers
22k
views
C tail call optimization
I often hear people say that C doesn't perform tail call elimination. Even though it's not guaranteed by the standard, isn't it performed in practice by any decent implementation anyhow? Assuming ...
- 68k
29
votes
2
answers
3k
views
Tail call optimization in Mathematica?
While formulating an answer to another SO question, I came across some strange behaviour regarding tail recursion in Mathematica.
The Mathematica documentation hints that tail call optimization might ...
- 18.2k
27
votes
2
answers
2k
views
Is there a technical reason that C# does not issue the "tail." CIL instruction? [duplicate]
Possible Duplicate:
Why doesn't .net/C# eliminate tail recursion?
Take the following C# code:
using System;
namespace TailTest
{
class MainClass
{
public static void Main (...
- 8,903
25
votes
2
answers
6k
views
Achieving Stackless recursion in Java 8
How do I achieve stackless recursion in Java?
The word that seems to come up the most is "trampolining", and I have no clue what that means.
Could someone IN DETAIL explain how to achieve stackless ...
- 462
22
votes
4
answers
6k
views
Why is Clojure much faster than Scala on a recursive add function?
A friend gave me this code snippet in Clojure
(defn sum [coll acc] (if (empty? coll) acc (recur (rest coll) (+ (first coll) acc))))
(time (sum (range 1 9999999) 0))
and asked me how does it fare ...
- 347
21
votes
3
answers
5k
views
What are some good ways of implementing tail call elimination?
I've written a small Scheme interpreter in an unholy mix of C/C++, but I have yet to implement proper tail calls.
I am aware of the classic Cheney on the MTA algorithm, but are there other nice ways ...
- 11.2k
20
votes
3
answers
5k
views
What is difference between tail calls and tail recursion?
I understand that tail recursion, is a special case where a function makes tail calls to itself.
But I do not understand how tail calls and tail recursion are different.
In “properly tail recursive” ...
- 1,386
20
votes
8
answers
12k
views
Differences between JVM implementations
Where do JVM Implementations differ (except licensing)?
Does every JVM implement Type Erasure for the Generic handling?
Where are the differences between:
JRockit
IBM JVM
SUN JVM
Open JDK
Blackdown
...
- 4,699
20
votes
4
answers
2k
views
What's the big deal with tail-call optimization and why does Python need it?
Apparently, there's been a big brouhaha over whether or not Python needs tail-call optimization (TCO). This came to a head when someone shipped Guido a copy of SICP, because he didn't "get it.&...
- 195k
19
votes
1
answer
2k
views
Will a properly implemented recursive lazy iterator function never stack overflow?
tl;dr;
In C#, do you have guarantees that a lazy iterator function that calls nothing but itself and does have a valid recursion exit condition will not cause a stack overflow?
Detailed question:
I ...
- 5,939
18
votes
1
answer
13k
views
Does Java support tail recursion? [duplicate]
Possible Duplicate:
Why does the JVM still not support tail-call optimization?
I see so many different answers online, so I thought I'd ask the experts.
- 10.4k
17
votes
1
answer
680
views
Tail Call Elimination in Clojure?
Can somebody rewrite this (plt) Scheme code into Clojure?
(define (f n)
(printf "(f ~a)~n" n)
(g n))
(define (g n)
(printf "(g ~a)~n" n)
(h n))
(define (h n)
(printf "(h ~a)~n" n)
...
- 1,035
17
votes
1
answer
334
views
Can/does the (forward) pipe operator prevent tail call optimization?
For a parameter optimization problem at work I wrote a genetic algorithm to find some good settings because a brute-force solution is unfeasible. Unfortunately, when I return in the morning, most of ...
- 2,945
16
votes
3
answers
4k
views
How do I know if a function is tail recursive in F#
I wrote the follwing function:
let str2lst str =
let rec f s acc =
match s with
| "" -> acc
| _ -> f (s.Substring 1) (s.[0]::acc)
f str []
How can I know if the ...
- 1,621
16
votes
2
answers
11k
views
Does Java 8 have tail call optimization?
I tried digging on the web to get my question answered. I found some documents related to Project DaVinci. This is tagged to the JSR 292 which is related to including closures in the JVM. Did this ...
- 2,557
15
votes
2
answers
5k
views
tail call optimization in lua
Lua claims that it implement tail call properly thus no stack needs to be maintained for each call thus allow infinite recursion, I tried to write a sum function, one is not tail call, and one is tail ...
- 6,663
14
votes
2
answers
3k
views
Does MATLAB perform tail call optimization?
I've recently learned Haskell, and am trying to carry the pure functional style over to my other code when possible. An important aspect of this is treating all variables as immutable, i.e. constants. ...
- 5,295
13
votes
2
answers
568
views
Why does tail call optimization need an op code?
So I've read many times before that technically .NET does support tail call optimization (TCO) because it has the opcode for it, and just C# doesn't generate it.
I'm not exactly sure why TCO needs an ...
- 120k
12
votes
1
answer
277
views
What is the purpose of the extra ldnull and tail. in F# implementation vs C#?
The following C# function:
T ResultOfFunc<T>(Func<T> f)
{
return f();
}
compiles unsurprisingly to this:
IL_0000: ldarg.1
IL_0001: callvirt 05 00 00 0A
IL_0006: ret
...
- 21.8k
12
votes
1
answer
463
views
Why is tail call optimization not occurring here?
We are using recursion to find factors and are receiving a StackOverflow exception. We've read that the C# compiler on x64 computers performs tail call optimizations:
JIT definitely does tailcals ...
- 137k
11
votes
7
answers
10k
views
Is it possible to force tail call optimization on GCC/Clang?
I'm trying to write a program in functional style with C as much as possible.
I know fine compilers like GCC/Clang do tail call optimization silently, but it's not guaranteed. Is there any option to ...
- 84.7k
11
votes
2
answers
1k
views
Tail optimization guarantee - loop encoding in Haskell
So the short version of my question is, how are we supposed to encode loops in Haskell, in general? There is no tail optimization guarantee in Haskell, bang patterns aren't even a part of the standard ...
- 70.5k
11
votes
2
answers
1k
views
F# tail call optimization with 2 recursive calls?
As I was writing this function I knew that I wouldn't get tail call optimization. I still haven't come up with a good way of handling this and was hoping someone else might offer suggestions.
I've ...
- 235
10
votes
3
answers
3k
views
F# has tail call elimination?
In this talk, in the first 8 minutes, Runar explains that Scala has problems with tail call elimination, this makes me wonder whether F# has similar problems ? If not, why not ?
- 20.5k
10
votes
4
answers
2k
views
Is it possible to use continuations to make foldRight tail recursive?
The following blog article shows how in F# foldBack can be made tail recursive using continuation passing style.
In Scala this would mean that:
def foldBack[T,U](l: List[T], acc: U)(f: (T, U) => ...
- 41.6k
10
votes
2
answers
622
views
Is the lack of tail call optimization an obstacle when using the Eventually workflow?
I'm using a modified version of the Eventually workflow from the F# spec for my development on Xbox. The .net framework on the Xbox does not support tail calls, it seems. Because of this, I have to ...
- 2,380
10
votes
2
answers
3k
views
Doing tail recursion in C++
My function can be written much more simply if I do a tail call recursion (as opposed to a for (;;)...break loop). Yet I'm afraid I'll have performance problems if the compiler fails to optimize it, ...
- 8,735
10
votes
2
answers
380
views
FoldRight over Infinite Structures in Scala using Trampolines
Let's start with a straightforward definition of foldRight:
def foldRight[T, U](base: U)(f: (T, => U) => U)(as: Seq[T]): U = {
as match {
case Nil => base
case head +: next => f(...
- 8,610
10
votes
5
answers
1k
views
vs2010 c++ tail call optimization
Consider the following code:
int fac_aux( int x, int res ) {
if( x == 1 ) return res;
else return fac_aux( x - 1, res * x );
}
int fac( int x ) {
return fac_aux( x, 1 );
}
int main() {
...
- 725
9
votes
5
answers
5k
views
tail-recursive function appending element to list
i've seen several examples of implementing append an element to a list, but all are not using tail recursion. how to implement such a function in a functional style?
(define (append-list lst elem)
...
- 3,777
9
votes
2
answers
768
views
Why is this F# sequence function not tail recursive?
Disclosure: this came up in FsCheck, an F# random testing framework I maintain. I have a solution, but I do not like it. Moreover, I do not understand the problem - it was merely circumvented.
A ...
- 8,950
8
votes
1
answer
1k
views
Erlang: stackoverflow with recursive function that is not tail call optimized?
Is it possible to get a stackoverflow with a function that is not tail call optimized in Erlang? For example, suppose I have a function like this
sum_list([],Acc) ->
Acc;
sum_list([Head|Tail],...
- 4,808
8
votes
2
answers
543
views
Why does the F# compiler not create a tail call for this function?
I'm having trouble with the fixed point combinator in F#:
let rec fix f a = f (fix f) a
fix (fun body num ->
if num = 1000000
then System.Console.WriteLine "Done!"
else body (num + ...
- 2,791
8
votes
3
answers
790
views
Optimizations by compiler in a recursive program
I got motivated from tail call optimization question What Is Tail Call Optimization?
So, I decided to see how can I do it in plain C.
So, I wrote the 2 factorial programs, 1st where tail call ...
- 1,109
8
votes
1
answer
715
views
What is the current state of tail-call-optimization for F# on Mono (2.11)?
What is the current state of Tail Call Optimization (TCO) implementation on Mono (2.11) ? Read somewhere that all the codebase would need to be modified to use a callee-pops-arguments convention. What ...
- 81
8
votes
1
answer
1k
views
About JSLint, its dislike of for loops, and tail call optimization
I noticed that the new version of JSLint doesn't like some forms of for loops. I found that to be strange, and started digging for some explanation. Under JsLint's help page, you can find this:
The ...
user4698813
7
votes
2
answers
2k
views
Is my rewritten foldl function optimised?
I just started Haskell 2 days ago so I'm not yet sure about how to optimise my code.
As an exercise, I have rewritten foldl and foldr ( I will give foldl here but foldr is the same, replacing last ...
- 189
7
votes
2
answers
753
views
Why does this code prevent gcc & llvm from tail-call optimization?
I have tried the following code on gcc 4.4.5 on Linux and gcc-llvm on Mac OSX(Xcode 4.2.1) and this. The below are the source and the generated disassembly of the relevant functions. (Added: compiled ...
- 249
7
votes
1
answer
309
views
What's some simple F# code that generates the .tail IL instruction?
I'd like to see the .tail IL instruction, but the simple recursive functions using tail calls that I've been writing are apparently optimized into loops. I'm actually guessing on this, as I'm not ...
- 73