Questions tagged [tail-call]
14 questions
49
votes
8 answers
What methods are there to avoid a stack overflow in a recursive algorithm?
Question
What are the possible ways to solve a stack overflow caused by an recursive algorithm?
Example
I'm trying to solve Project Euler problem 14 and decided to try it with a recursive algorithm. However, the program stops with a…
Lernkurve
- 817
- 1
- 7
- 14
38
votes
4 answers
What limitations does the JVM impose on tail-call optimization
Clojure does not perform tail call optimization on its own: when you have a tail recursive function and you want to have it optimized, you have to use the special form recur. Similarly, if you have two mutually recursive functions, you can optimize…
Andrea
- 5,355
- 4
- 31
- 36
22
votes
3 answers
Which are the alternatives to using a stack to represent function call semantics?
We all know and love that function calls are usually implemented using the stack; there are frames, return addresses, parameters, the whole lot.
However, the stack is an implementation detail: calling conventions may do different things (i.e. x86…
Lorenzo Dematté
- 678
- 1
- 5
- 14
20
votes
2 answers
Y combinator and tail call optimizations
The definition of a Y combinator in F# is
let rec y f x = f (y f) x
f expects to have as a first argument some continuation for the recursive subproblems.
Using the y f as a continuation, we see that f will be applied to successive calls as we can…
nicolas
- 349
- 1
- 7
15
votes
4 answers
When there's no TCO, when to worry about blowing the stack?
Every single time there's a discussion about a new programming language targetting the JVM, there are inevitably people saying things like:
"The JVM doesn't support tail-call optimization, so I predict lots of exploding stacks"
There are thousands…
Cedric Martin
- 1,067
- 10
- 16
4
votes
1 answer
Tail-recursive implementation of take-while
I am trying to write a tail-recursive implementation of the function take-while in Scheme (but this exercise can be done in another language as well). My first attempt was
(define (take-while p xs)
(if (or (null? xs)
(not (p (car xs))))
…
Giorgio
- 19,486
- 16
- 84
- 135
4
votes
1 answer
Tips for Tail Call Recursion in Python
Ok, Python doesn't have tail call optimization.
But for those who think better recursively than "looply", whats the best practices to write code??
1000 stack calls are enough for many cases, but what are the tips to conceal recursion with efficiency…
Lucas Ribeiro
- 141
- 1
- 3
3
votes
2 answers
When to use tail recursion?
I've recently gotten into functional programming. I asked a question earlier over here "'Remembering' values in functional programming" and learned a lot of things I hadn't even realized I wanted to learn yet. It was very useful. It did leave me…
Ucenna
- 1,292
- 2
- 10
- 19
3
votes
3 answers
What can qualify for potential tail call recursion (TCO) optimization or tail recursion elimination (TRE)
Short question is: what can qualify for potential tail call recursion optimization (TCO) or tail recursion elimination (TRE) if the compiler or interpreter supports it.
The summary of this question is in the section "Or is it true that, one simplest…
nonopolarity
- 1,827
- 1
- 16
- 30
2
votes
3 answers
Are lessons on tail recursion transferable to languages that don't optimize for it?
I'm currently reading through Structure and Interpretation of Computer Programs (SICP). During the course of that book, the lesson of "you can optimize recursive procedures by writing them as tail recursive" is drilled in to the reader again and…
J. Mini
- 997
- 8
- 20
2
votes
1 answer
Different Implemenations of Tail Call Optimisation
I've heard some people in my university discuss the tail call optimisation in ML as if it were a special version tail call optimisation.
Does the ML (SML/F#) implementations of tco in these languages differ substantially from the implementation in…
calben
- 611
- 6
- 11
2
votes
2 answers
General recursion to tail-recursion
Is it theoretically possible to transform every kind of general-recursion into tail-recursion? Are they equivalent for example from a lambda-calculus point of view? That's a debate between me and an acquaintance.
My view is that it's not possible…
user131411
- 121
- 1
1
vote
1 answer
Continuations, coroutines, and tail-call optimization
I am trying to learn continuations and use them to implement coroutines in Scheme.
I have two procedures (coroutines) a and b, and I switch between them in the following way:
;; c is a continuation.
(define (a c)
...
;; Switch to the other…
Giorgio
- 19,486
- 16
- 84
- 135
0
votes
0 answers
If a delegate contains a tail call request, what happens?
Simply put, what happens when I have a delegate, that delegate contains a method with a tail call request, and then I call it from a non-tail position?
If I called the method directly, it would discard the existing params and reuse stack space. Does…
Telastyn
- 108,850
- 29
- 239
- 365