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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
30 views

Tail call optimization for procs possible?

I see that tail call optimization can be enabled in ruby and that it works with method calls following these instructions, but I need it to work for Procs too for use with blocks/lambdas, since only ...
1 vote
1 answer
103 views

Converting a simple recursive haskell function to be tail recursive

2 weeks new to haskell and functional programming. In the process of covering foldl and foldr in class, I found that I was quite new to tail recursion and never actually tried writing a tail recursive ...
  • 25
1 vote
0 answers
82 views

Tail-calls corrupted when compiled with __attribute__((musttail))

I was working a Lisp interpreter with a 'threaded' design, where it compiles to a VM where each instruction is a C function that calls the next instruction — if the compiler does tail call elimination,...
0 votes
1 answer
55 views

Why does clang have trouble with optimizing tail calls in destructors?

Here is a simplified singly-linked list, where each node owns the next, along with a function for destroying the list: struct Node { Node* next = nullptr; ~Node() { delete next; } }; void ...
  • 5,577
10 votes
2 answers
286 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(...
0 votes
1 answer
65 views

Tail call stack

I'm having trouble understanding the Stack manipulation needed in order to implement Tail call in assembly language. When we have a Tail call to function We basically want to override the current ...
1 vote
2 answers
73 views

Question regarding tail call optimization

As far as I know, there is a prerequisite for performing tail call optimization is that the recursion point should be the last sentence in the function, and the result of the recursive call should be ...
  • 1,826
0 votes
1 answer
87 views

Tail call optimization with eigen

I'm trying to make the compiler tail-call optimize eigen-expressions that are passed recursively. The following will optimize using GCC -O2: inline double recursive(const double &A, ...
1 vote
0 answers
38 views

JavaScript: how do I improve this repeat function using tail call optimization

Here is a repeat function that recursively calls itself const repeat = x => f => { if (x > 0) { f() return repeat (x - 1) (f) } } The problem with it is it can ...
  • 4,373
1 vote
1 answer
213 views

Are tail calls on diverging functions optimized in Rust?

If I have the following functions: fn a() -> ! { b() } fn b() -> ! { loop {} } Does Rust optimize such calls to simple jumps? I have looked at a Playground to show the assembly, but a ...
-2 votes
1 answer
69 views

Why is this tail-call optimized method not recognized as such by the Scala compiler?

This simple regex implementation (scastie here) does not compile, where I expected it to. The error is at line 14, where an intermediate recursive call is interpreted as to break the @tailrec ...
0 votes
1 answer
62 views

print a newline using tail call optimization

There's this unanswered question in the Igor Zhirkov's book Low-Level Programming : "Try to rewrite print_newline without calling print_char or copying its code. Hint: read about tail call ...
  • 3,372
3 votes
1 answer
171 views

Why does non-trivial destructor of return type prevent tail-call optimization?

Currently, in C++ compilers one of the rules for tail-call optimization is that the return type must be trivially destructible. (Based on analyzing GCC, Clang trunk behavior. MSVC has troubles with ...
  • 1,005
1 vote
3 answers
140 views

How I could use tail call optimisation on this combination function?

My exercise, that you can see here, says that I need to implement a recursive version of C(n, k). That's my solution: module LE1.Recursao.Combinacao where combina :: Integral a => a -> a -> ...
  • 417
2 votes
0 answers
148 views

Tail call optimization in ifort vs gfortran

I have some code that when is compiled with gfortran, a tail call optimization is done, but when compiled with ifort, it isn't. Here are some very simple snips describing the issue: gfortran ifort ...
1 vote
1 answer
199 views

Is there a way to optimize tail calls in Scala?

I am aware that Scala has optimizations for tail-recursive functions (i.e. those functions in which the recursive call is the last thing executed by the function). What I am asking here is whether ...
  • 119
0 votes
2 answers
67 views

Can JavaScript function call subexpressions be tail calls?

Consider the following return statement: return f() || g(); The call f() obviously is not a tail call, because the function does not actually return if f() is falsy. What about the g() part though, ...
5 votes
2 answers
209 views

Will this be tail call optimized in SWI-Prolog

step_n(0, I, I). step_n(N, In, Out) :- N > 0, plus(N1, 1, N), phase_step(In, T), step_n(N1, T, Out). phase_step is a function that transforms data. Will this step_n run in almost the same ...
  • 3,430
2 votes
1 answer
197 views

How to convert a variation of ackermann function to support tail call?

I'm currently solving a problem which is to implement a variation of ackermann function in scala with tail call optimization support so that the stack does not overflow. The problem is, I cannot find ...
1 vote
3 answers
286 views

Scheme: Iterative process to reconstruct a list in original order?

My question is: how to write a procedure that utilises tailcall, and that constructs a list not in the reverse order. To show what I mean, here is an example of a very simple procedure that is ...
  • 485
2 votes
1 answer
276 views

Why does this kind of tail call of fibonacci run faster than pure tree recursion in Haskell?

I'm trying to undestand tail call recursions. I convert pure tree-recursion fibonacci function: fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2) to a tail call version: fib' 0 a = a fib' 1 a = 1 + ...
  • 55
0 votes
2 answers
170 views

Get results for sub problems using tail call recursion in Scala

I am trying to calculate results for each sub problem using @tailrec similar to how normal recursive solutions can produce solutions for each sub problem. Following is the example I worked on. @...
  • 881
0 votes
1 answer
571 views

Telling GCC to tail-call a function

Let's say I've got a C function: unsigned int fact(unsigned int n, unsigned int acc) { if(n > 0) return fact(n - 1, n * acc); return acc; } Is there a way to tell GCC to tail call the ...
  • 1,304
2 votes
0 answers
454 views

Use of thunks, trampolines and continuation passing in python

I came to know about the concept of Tail Call Optimization(TCO) from this blog: Sing Me A Song of Stack Overflow: A Musical Tail Call Optimization. Going into this concept(or "feature" or "...
  • 1,772
2 votes
0 answers
1k views

Why is my tail call-optimized implementation faster than the normal recursive if it's not supported in c#?

I recently got introduced to the concept of tail-call optimization and as far as I can read it's not inherently supported in the .NET compiler but there is a workaround called "Trampolining" which I'...
  • 923
2 votes
2 answers
280 views

Erlang, Last Call Optimization, lambda functions, and how to prevent growing a stack

I'm writing some Erlang code, and I've run into a bizarre situation that I don't understand. The code: -module(recursive_test). -export([a/2]). a(_, []) -> ok; a(Args, [H|T]) -> F = fun() ...
3 votes
2 answers
183 views

Do bound functions support proper tail calls in ES6?

In the ECMAScript 2015 Language Specification, the definitions of Function.prototype.apply and Function.prototype.call both include "Perform PrepareForTailCall()" as one of their steps, so we know ...
  • 1,774
3 votes
1 answer
121 views

Tail recursion [C]

The question in my book is "Which of the recursive calls (not functions!) are tail recursive?" unsigned f(unsigned x) { if(x==0) return 1; else if(x==1) return f(x-1); else return 3*x ...
3 votes
1 answer
148 views

Compiler Friendly Tail Recursion + Tail Recursion Checking in ATS

What is the best way to check that a function has been tail call optimized in ATS? (So far I have been running "top" to see if memory usage is constant) As a follow up: Say you have a complex tail-...
0 votes
1 answer
437 views

How can I tell if my function has been tail call optimized?

I'm reading section 2.8 (Tail Recursion) in On Lisp. It has an example of a tail recursive function: (defun our-length-tr (lst) "tail recursive version with accumulator" (labels ((rec (lst acc) ...
1 vote
3 answers
90 views

how to insert in the middle of a list, being tail-call friendly but without hurting performance?

So I have this function which seems to be non-tail-call friendly, right? let rec insertFooInProperPosition (foo: Foo) (bar: list<Foo>): list<Foo> = match bar with | [] -> [ foo ...
1 vote
2 answers
916 views

tail rec kotlin list

I'm trying to do some operations that would cause a StackOverflow in Kotlin just now. Knowing that, I remembered that Kotlin has support for tailrec functions, so I tried to do: private tailrec fun ...
6 votes
1 answer
268 views

Why does gcc perform tail call optimization for one version but not for the other?

Experimenting with tail call optimization (tco), I stumbled upon the following curious example: unsigned long long int fac1(unsigned long long int n){ if (n==0) return 1; return n*fac1(n-1); }...
  • 32.1k
6 votes
1 answer
1k views

Elixir tail-call recursive function

I have this function that finds the even numbers in a list and returns a new list with only those numbers: def even([]), do: [] def even([head | tail]) when rem(head, 2) == 0 do [head | ...
  • 325
5 votes
1 answer
83 views

Is there a tco pattern with two accumulating variables?

Just for fun (Project Euler #65) I want to implement the formula n_k = a_k*n_k-1 + n_k-2 in an efficient way. a_k is either 1 or (* 2 (/ k 3)), depending on k. I started with a recursive solution: ...
63 votes
5 answers
33k 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 ...
0 votes
1 answer
98 views

Is continuation style implementation of factorial tail call optimized (TCO)?

Here are two factorial implementation from this site: Tail Call Optimized (TCO): function fact(n) { return tail_fact(n,1) ; } function tail_fact(n,a) { if (n == 0) return a ; else ...
4 votes
1 answer
567 views

How 'smart' is GCC's Tail-Call-Optimisation?

I just had a discussion where the following two peices of C code were being discussed: For-Loop: #include <stdio.h> #define n (196607) int main() { long loop; int count=0; for (loop=0;...
  • 4,271
4 votes
3 answers
2k views

Tail recursion in NodeJS

So I recently came across case I needed to write code where callback calls itself and so on and wondered about NodeJS and tail-call support, so I found this answer https://stackoverflow.com/a/30369729 ...
user avatar
12 votes
1 answer
423 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 ...
2 votes
0 answers
113 views

Does Gforth optimize proper tail calls?

I have the following (somewhat inefficient) code: \ RNG support VARIABLE seed : rand ( -- random ) seed @ DUP 13 LSHIFT XOR DUP 17 RSHIFT XOR DUP 5 LSHIFT XOR DUP seed ! ; \ Checker for number of ...
  • 2,980
2 votes
1 answer
211 views

Prolog Tail call optimization for flattening a tree

I want to flatten a tree in prolog using tail recursion.I have done it with append list with recursive calls. I want to optimize my version. This is my function which uses recursive call.I want to ...
3 votes
3 answers
411 views

At which stage should I implement tail call optimization for my compiler

I wrote a small compiler in Racket for a scheme-like language. Now I want to implement TCO for my compiler. My idea is: I need to detect tail calls before transform them into intermedia ...
  • 1,169
1 vote
3 answers
313 views

Using Default Optional argument and recur together in Clojure

I am able to set a default argument and do a regular recursion with it, but for some reason I cannot do with recur for tail optimization... I keep getting an java.lang.UnsupportedOperationException: ...
0 votes
1 answer
291 views

Haskell: TCO and Lazy evaluation

I'm trying to understand why the first main does not terminate when c is not valid, while the second terminates. From the description here main is just an unevaluated thunk, and executing it is just ...
  • 1,449
1 vote
1 answer
570 views

Disable tail calls to a function in Visual Studio

How can I disable tail calls to a specific function in Visual Studio? The reason I need this is because I have a function that breaks to the debugger that I use when an error occurs and I need to see ...
  • 30.4k
3 votes
1 answer
62 views

What reasoning lead to `Sequence expression containing recursive definition is compiled incorrectly`

The question Stack overflow despite tail call position but only in 64-bit lead to uncovering a bug in the F# compiler. After reading the answer I am curious as to the reasoning that lead to finding ...
  • 24.4k
17 votes
1 answer
316 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,793
1 vote
0 answers
312 views

Octave/Matlab - tail call optimization for tail recursive lambda function

I am trying to write recursive anonymous function, so far what works for me is to use the Y combinator. %{ Call lambda function with any number of arguments. %} call_ = @feval; %{ Internal ...
  • 483
6 votes
2 answers
2k views

What is the difference between loop/recur and recur by itself?

I'm having trouble finding the answer to this in the Clojure docs. I'm new to Clojure and it seems as though you can use recur in two different ways and essentially get the same result. Example 1: (...