Stack Overflow
Stack Overflow

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.

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.

This Stack Overflow question gives more insight: What Is Tail Call Optimization?

172 questions
1076
votes
10 answers

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?
majelbstoat
  • 12,889
  • 4
  • 28
  • 26
109
votes
3 answers

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 mode (for instance using :load under REPL)?
huynhjl
  • 41,520
  • 14
  • 105
  • 158
104
votes
4 answers

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 functions: --tail recursive fac :: (Integral a) => a ->…
haskell rascal
  • 1,143
  • 2
  • 8
  • 7
98
votes
5 answers

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 interest from Sun's/Oracle's side in supporting tail…
soc
  • 27,983
  • 20
  • 111
  • 215
81
votes
3 answers

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 projects, I already came across a few functions that…
JustSid
  • 25,168
  • 7
  • 79
  • 97
76
votes
2 answers

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 does it so in a more interesting case below? func…
Alfa07
  • 3,314
  • 3
  • 26
  • 39
63
votes
5 answers

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 replacement for while loops since tail call optimization is…
David Moneysmith
  • 799
  • 2
  • 8
  • 10
51
votes
4 answers

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?
dxuhuang
  • 990
  • 1
  • 9
  • 18
46
votes
5 answers

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) result else fact(n - 1, n *…
Seth Tisue
  • 29,985
  • 11
  • 82
  • 149
38
votes
2 answers

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?
James McMahon
  • 48,506
  • 64
  • 207
  • 283
37
votes
4 answers

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.js, it causes a stack overflow: function foo(x)…
Koz Ross
  • 3,040
  • 2
  • 24
  • 44
35
votes
8 answers

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 you're only targeting mature, well implemented…
dsimcha
  • 67,514
  • 53
  • 213
  • 334
29
votes
2 answers

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 be performed. But my own experiments give…
WReach
  • 18,098
  • 3
  • 49
  • 93
27
votes
2 answers

Is there a technical reason that C# does not issue the "tail." CIL instruction?

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 (string[] args) { Counter(0); …
Justin
  • 8,853
  • 4
  • 42
  • 42
24
votes
2 answers

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 recursion in Java? Also, what is "trampolining"?…
Matthewacon
  • 360
  • 3
  • 15
1
2 3
…
11 12