Stack Overflow
Stack Overflow

Questions tagged [tail-recursion]

Tail recursion is a recursive strategy in which a function does some amount of work, then invokes itself. The "tail" refers to the fact that the recursion is at the very end of the function. Many -- especially functional -- programming language compilers can turn these types of calls into iteration, meaning tail recursion in supported languages can be used without fear of a stack overflow, regardless of the number of calls.

Tail recursion is a recursive strategy in which a function does some amount of work, then invokes itself. The "tail" refers to the fact that the recursion is at the very end of the function. Many (especially functional language) compilers can turn these types of calls into iterative calls, meaning tail recursion can be used without fear of a stack overflow, regardless of the number of calls.

1348 questions
2033
votes
29 answers

What is tail recursion?

Whilst starting to learn lisp, I've come across the term tail-recursive. What does it mean exactly?
Ben Lever
  • 2,023
  • 7
  • 26
  • 34
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
309
votes
19 answers

How do I break out of a loop in Scala?

How do I break out a loop? var largest=0 for(i<-999 to 1 by -1) { for (j<-i to 1 by -1) { val product=i*j if (largest>product) // I want to break out here else …
TiansHUo
  • 8,509
  • 7
  • 45
  • 57
288
votes
8 answers

Does Python optimize tail recursion?

I have the following piece of code which fails with the following error: RuntimeError: maximum recursion depth exceeded I attempted to rewrite this to allow for tail recursion optimization (TCO). I believe that this code should have been…
Jordan Mack
  • 8,223
  • 7
  • 30
  • 29
237
votes
20 answers

Understanding recursion

I'm having major trouble understanding recursion at school. Whenever the professor is talking about it, I seem to get it but as soon as I try it on my own it completely blows my brains. I was trying to solve Towers of Hanoi all night and completely…
Confused
  • 2,395
  • 3
  • 14
  • 3
167
votes
5 answers

Which, if any, C++ compilers do tail-recursion optimization?

It seems to me that it would work perfectly well to do tail-recursion optimization in both C and C++, yet while debugging I never seem to see a frame stack that indicates this optimization. That is kind of good, because the stack tells me how deep…
Magnus Hoff
  • 21,529
  • 9
  • 63
  • 82
126
votes
8 answers

How exactly does tail recursion work?

I almost understand how tail recursion works and the difference between it and a normal recursion. I only don't understand why it doesn't require stack to remember its return address. // tail recursion int fac_times (int n, int acc) { if (n ==…
Alan Coromano
  • 24,958
  • 53
  • 135
  • 205
125
votes
7 answers

Why doesn't .NET/C# optimize for tail-call recursion?

I found this question about which languages optimize tail recursion. Why C# doesn't optimize tail recursion, whenever possible? For a concrete case, why isn't this method optimized into a loop (Visual Studio 2008 32-bit, if that matters)?: private…
ripper234
  • 222,824
  • 274
  • 634
  • 905
105
votes
5 answers

Are functions in JavaScript tail-call optimized?

I have been trying to understand Tail call optimization in context of JavaScript and have written the below recursive and tail-recursive methods for factorial(). Recursive: function factorial (n) { if (n < 2) { return 1; } else { return…
Aditya Singh
  • 15,810
  • 15
  • 45
  • 67
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
99
votes
5 answers

Does the JVM prevent tail call optimizations?

I saw this quote on the question: What is a good functional language on which to build a web service? Scala in particular doesn't support tail-call elimination except in self-recursive functions, which limits the kinds of composition you can do…
Jason Dagit
  • 13,684
  • 8
  • 33
  • 56
95
votes
5 answers

Does Ruby perform Tail Call Optimization?

Functional languages lead to use of recursion to solve a lot of problems, and therefore many of them perform Tail Call Optimization (TCO). TCO causes calls to a function from another function (or itself, in which case this feature is also known as…
Charlie Flowers
  • 17,338
  • 10
  • 71
  • 88
94
votes
6 answers

Are any JavaScript engines tail call (TCO) optimized?

I have a tail recursive pathfinding algorithm that I've implemented in JavaScript and would like to know if any (all?) browsers would possibly get stack overflow exceptions.
clofresh
  • 1,345
  • 1
  • 9
  • 11
84
votes
7 answers

foldl is tail recursive, so how come foldr runs faster than foldl?

I wanted to test foldl vs foldr. From what I've seen you should use foldl over foldr when ever you can due to tail reccursion optimization. This makes sense. However, after running this test I am confused: foldr (takes 0.057s when using time…
Ori
  • 4,961
  • 10
  • 40
  • 39
79
votes
9 answers

Functional Programming - Lots of emphasis on recursion, why?

I am getting introduced to Functional Programming [FP] (using Scala). One thing that is coming out from my initial learnings is that FPs rely heavily on recursion. And also it seems like, in pure FPs the only way to do iterative stuff is by writing…
peakit
  • 28,597
  • 27
  • 63
  • 80
1
2 3
…
89 90