Practically the day after I learned about tail recursion in CS class, I learned that almost all recursive calls can be translated to iteration, that in many cases the iterative version is easier to scan, is as fast if not faster, and that they can usually handle much much larger inputs than recursion due to avoiding stack overflow.
Tail recursion is meant to fix the latter. But what we mean to happen and what actually happens ain't ever exactly similar.
Tail recursion IME is a bigger foot gun than relying on someone to add a new conditional branch at the end of a block in an iterative algorithm without fucking it up in the process. And iteration responds generally better to Extract Function. And while I can think of counter cases easily enough, in the large iteration is less work and less vigilance. And you cannot scale a project up without the vigilance requirement amortizing basically to 0 per line of code.
I have my doubts about any CS class/lecture, that teaches, that the "iterative version is easier to scan". Might just be the bias or inexperience of the lecturer. By not I find recursive to be often easier to read than some for loop with its loop header and counter that I need to think about and update in my mind. And then the loop usually in many languages does not even have a return value, because it is not an expression, but a statement. Meeehhh, very meehhh in many languages. Not all, but many.
I think maybe in languages like Ruby or Smalltalk a loop can be more readable, because of how they structure it as messages to objects, rather than special keywords in the language.
E.g. scala has @tailrec annotations, which make it a compile error for the annotated function to not be tail recursive. Clojure doesn't have tail call elimination, but has the `recur` special form for explicit recursion that is guaranteed to not consume any stack space.Rust has reserved the `become` keyword that will eventually guarantee tail call elimination (So pretty similar to Clojure's recur, but I think Rust's version will allow mutual recursion)
Zig goes the whole hog, and has `@call(modifier, fn, args)`, where `modifier` can be things like compile_time, always_tail, always_inline, never_tail, never_inline, and a bunch other desirable guarantees you might want.
> Practically the day after I learned about tail recursion in CS class, I learned that almost all recursive calls can be translated to iteration, that in many cases the iterative version is easier to scan, is as fast if not faster, and that they can usually handle much much larger inputs than recursion due to avoiding stack overflow.
What do you mean by easier to scan? I find (most) loops [0] hard to read, because they typically involve mutable state.
When properly implemented, tail calls are as fast as gotos and loops, and don't blow up any stack. (Not all languages are implemented with a stack in any case.)
However you have one point:
Most of the time, we don't use recursion directly in our programs even in a language like Haskell or Scheme. Instead we define a 'combinator' that encapsulates the specific, limited recursion scheme that we want, and then use that one. This is very similar to how people generally don't use goto directly in their programs.
You might be familiar with the combinators 'map', 'filter' and perhaps 'reduce'/'foldr'. You could re-interpret the various common loop types as such recursion combinators that weaker languages have to bake into their language, because they are not strong enough to express them as a user-defined library. And indeed, Haskell has Control.Monad.Loops (https://hackage.haskell.org/package/monad-loops-0.4.3/docs/C...) which gives you exactly the common loop types as a library.
Some examples of less common combinators are eg 'unfold' or various combinators to traverse trees or graphs.
[0] The foreach-loop over some sequence is less headache inducing than eg a while-loop.
There are cases where iteration is clearer, and there are cases where recursion is clearer.
It's well worth being familiar with both - if you learn how to shoehorn both approaches where they aren't ideal, your judgement on avoiding such practices will improve. :)
I'm a pretty big functional programming nerd and I want to like tail recursion, but I honestly kind of feel like I agree with Guido on it, which is that it kind of breaks the typical stack-trace patterns.
I have kind of grown to prefer Clojure's loop/recur construct, since it gives you something more or less akin to tail recursion but it doesn't pretend to be actually recursive.
> ..kind of breaks the typical stack-trace patterns.
The expectation that iterative recursion ought to have a call stack is the problem here and wouldn't be up for debate if people had done their due diligence and read their SICP.
Every developer should know how to write a tail-recursive function and understand why it is equivalent to a loop. That said, tail recursion is rarely needed in modern functional programming. For example, why write out a recursive function when a call to `fold` or `map` will do the same thing?
I wouldn't say "rarely", unless you have a whole host of other higher order functions at your disposal for more special cases than map and fold. There are many cases, where you don't want to fold or map over the whole data structure and want to exit early with a result already. Writing tail recursive functions is still very common.
> I wrote up a detailed blog post about tail call optimization in Elixir/Erlang and its performance. The TLDR; sort of is that none tail call optimized recursive functions (body-recursive) can be faster and more memory efficient than TCO functions. This is something that I never thought before, that TCO is always faster seems to be a common misconception. My example is also not contrived - it’s an implementation of map.
Tail recursion is beautifully deep and simple. It (and as a corollary CPS) makes clear what state matters to your loop (and function) and avoids extraneous variables in loops as well as implicit unneeded state in functions. It also makes it easier to show the correctness of your loops. Sure, there are other functional language constructs like fold and map, if your problem is amenable to them. Tail recursion is more general and simpler.
I have almost the opposite view: tail calls are great.
But most of the time you will want to express your program in terms of more restricted combinators, because restriction makes the readers job easier. Easier to understand, and easier to convince yourself that no weird things are happening.
Basically, you might already agree that restricting mutation is good. This is the same principle.
So when you see a 'fold' you know even without looking at the callback, that your program will run through the whole list and not exit early. When you see a 'map' you also know that no early exit will happen, but even more you know exactly how the return value will be constructed (whereas for fold that's arbitrary).
However you are right that 'fold' and 'filter' and 'map', just like 'for' and 'while', are not good as universal building blocks.
That's why you should define new combinators when you need them. Typically, that's when you define new data structures, eg when you define a tree you will also want to define a 'map' for it, and also various tree traversals and perhaps searches. Less typically, you also want new combinators for new algorithmic ideas, even on old data structures.
Eg matrix multiplication is an interesting combinator. You provide the meaning of 'addition' and 'multiplication' as call-backs, and depending on your choice you get an algorithm for finding shortest paths or for matching regular expressions etc (in addition to the obvious matrix-multiplication on real numbers, of course). See https://news.ycombinator.com/item?id=9751987
And a must-have in Erlang/OTP (and Elixir of course) where you can "loop" passing the altered state as a parameter. I love it. And wish that all languages implement TCO. That's one of the reason I also like Scheme.
I disagree with the title; loops are tail-recursive functions, but tail-recursive functions are not loops (in the sense that squares are rectangles, but rectangles are not squares).
It is true that every tail recursive function can be converted into a semantically equivalent loop via a transformation like CPS (which the author mentions). However, for mutually tail-recursive functions, this conversion loses control flow information. This is because after the CPS transformation, calls to the other function become calls to a continuation; this call usually must be implemented as an indirect jump. On the other hand, mutually tail-recursive functions can call each other with direct/statically-known jumps.
This loss of information might appear trivial, but in practice it has some important consequences. Classic examples are interpreter loops. It is well-known that computed gotos can result in modest to large speedups for interpreters [1]. The reason why is that computed gotos create an indirect jump per opcode, so a branch predictor can take advantage of correlations between opcodes. For example, looking at Python disassembly, the header of a standard range for loop compiles down to three opcodes: GET_ITER, FOR_ITER, STORE_FAST in sequence [2]. A branch predictor can recognize that the target of the "FOR_ITER" indirect jump will likely be the "STORE_FAST" instruction pointer; it cannot predict this in the naive implementation where jumps for all instructions are "merged" into a single indirect jump / switch at the top of the loop body. In this case, computed goto is effectively equivalent to a CPS transformation whose closures require no storage on the heap.
Suppose, however, we know even more information about the instruction sequence; for example, we know ahead of time that every FOR_ITER opcode will be followed by a STORE_FAST opcode. We could completely replace the indirect jump with a direct jump to the instruction pointer for the STORE_FAST opcode. Because modern branch predictors are very good, this will have about the same performance in practice as the computed goto loop.
However, consider the limiting case where we know the entire instruction sequence beforehand. If we write our interpreter as many mutually tail-recursive functions, with one function for every instruction, an optimizing compiler can replace every indirect call with a direct (tail-recursive) call to the function that implements the next instruction's opcode. With a good enough optimizer / partial evaluator, you can turn an interpreter into a compiler! This is known as the first Futamura projection [3].
To see an example of this in action, I wrote a prototype of a Brainfuck compiler via the Futamura projection; it uses LLVM as a partial evaluator [4]. The main interesting function is `interpret`, which is templated on the program counter / instruction. That is, `interpret` is really a family of mutually tail-recursive functions which statically call each other as described above. For short Brainfuck programs, the LLVM optimizer is able to statically compute the output of the Brainfuck program. (The one in the Godbolt link compiles to a loop, likely because LLVM does not want to unroll the mutual recursion too much.) You can play around with different Brainfuck programs by modifying the `program` string on line 5.
The analogy is inverted - tail-recursive functions are a superset of loops (rectangles include squares), not vice versa. Loops can always be expressed as tail-recursive functions, but tail-recursive functions (particularly mutually recursive ones) can express control flow patterns that simple loops cannot without additional machinery.
Several people in this thread are saying that tail recursion is superior to imperative iteration in that it explicitly specifies which variables may change in each iteration (assuming a broadly immutable language).
To the contrary, I'd argue that immutability isn't the only alternative to universal mutability: many newer imperative languages (such as Rust) have various forms of controlled mutability, where one must explicitly declare which variables may be modified by imperative assignments.
IME, controlled mutability captures just about all the benefit of immutable languages, without requiring any special data structures or sufficiently-smart compiler analyses to ensure good performance. I've never really understood the desire for tail-recursive versions of iterative algorithms, except for a prior commitment to functional programming.
But Rust's semantics make it less ergonomic to pass values and especially once you do any mutation, that code path is no longer trivially up for parallelization/concurrency. There one will have to lean into what Rust offers to make it safe again, which brings along more syntax. When one wants to pass values, one needs to implement clone or copy or something, and then explicitly clone or copy or so.
It is a tradeoff one can make, and it lends itself to high performance but it does come at a cost.
Loops and gootos are just a special case of function calls, that needed to be invented because back in the olden days we had no clue how to design language and write compilers.
I don't understand why someone would want to hold on nostalgically to restrictions we no longer face.
Controlled mutability is a step up, yes. Btw, even languages like Haskell give you plenty of mutability to play with, if you want to. (Eg MVars and TVars are a thing.)
You are right that replacing a loop one for one with a tail recursive version doesn't give you much benefit either way. (Though it does make my life easier, because you don't have to contort my brain around keeping track of mutation.)
However that's a bit of a straw man and misses the broader picture.
What you'd want to do is define combinators that encapsulate the specific pattern of computation you want to implement. The most commonly known combinators are things like 'map' and 'filter'. But there are plenty more useful ones you can define, like various tree traversals or whatever makes sense for use cases and data structures.
Whether those combinators are implemented with tail calls or with loops or gotos or whatever is an implementation detail that their users don't need to worry about.
> I've never really understood the desire for tail-recursive versions of iterative algorithms, except for a prior commitment to functional programming.
Tail-recursion and iteration are broadly equivalent right? So picking one over the other is a matter of style and capability.
You can't use iteration if your language isn't capable of it, but no worries, you can use tail recursion.
Similarly, you can't use tail recursion if your language isn't capable of it, but no worries, you can use iteration, at least for iterative tail recursion. Otoh, there are uses of tail call elimination that aren't recursion (or aren't direct recursion) ... that can get akward if your language can't manage it.
Tail recursive functions are loops when tail calls are jumps.
Tail calls being jumps is the key insight.
Not all tail calls are recursion!
Students are confused by recursion. Some may be confused by tail calls.
Don't mix two confusing things together when teaching.
(Tail calls get mixed up with recursion because recognizing and treating/optimizing recursive tail calls to create loops an important highlighted category. In a compiler that doesn't optimize tail calls, optimizing self tail calls is an important priority (if that is easier to do than a general treatment). Many common algorithms are expressible in just one function that calls itself, and there are cases in which some or all of those calls can be tail calls; e.g. binary tree traversal.)
The order should probably be: teach recursion first. Then when students have firmly wrapped their heads around it, introduce tail calls. Students will gain the skill of knowing what is a tail call and why it is important, and recognize which calls tail calls. Secondly, the harder skill of taking recursion that uses non-tail calls and restructuring it to make tail calls instead.
Everybody knows that "goto is harmful" but who has noticed that the very same paper says that loops are technically unnecessary?
Loops are merely a special case of recursion. The reason languages have loops is that reifying these cases to language constructs simplifies code generation. The downside is that it muddles the logic of computation.
Did Python ever get tail recursion? There was a big controversy years ago. Guido didn't like it. But apparently something went in.
Enthusiasm for tail recursion comes mostly from LISP and LISP-adjacent people - those who learned to program from SICP.[1] This is neither good nor bad. Even MIT doesn't use SICP any more, though.
(The classic 20th century "programming should be hard and programmers should suffer" books:
- Structure and Interpretation of Computer Programs, Abelson and Sussman.
- Fundamental Algorithms and Semi-Numerical Algorithms, Knuth.
- Algorithms + Data Structures = Programs, Wirth.
- A discipline of programming, Dijkstra.
These are mostly of historical interest now, but at one time, knowing those defined a real computer scientist. Today, it's more important that your LLM has been trained on them.)
More exciting in my mind than the equivalence between tail recursion and while loops is the equivalence between left folds and for loops. A for loop in its most general shape is something like
<whatever state the application is in here serves as the starting state>
foreach (i in range(n)) {
<the state of the application is updated with each iteration>
}
<the desired state of the application has been applied when the loop is done>
The difference is that the starting state is given explicitly to the loop, and the desired state is returned as a composite value. This makes it easier to troubleshoot than the implicit state transitions, but it's essentially the same still.
33 comments
[ 2.7 ms ] story [ 45.6 ms ] threadTail recursion is meant to fix the latter. But what we mean to happen and what actually happens ain't ever exactly similar.
Tail recursion IME is a bigger foot gun than relying on someone to add a new conditional branch at the end of a block in an iterative algorithm without fucking it up in the process. And iteration responds generally better to Extract Function. And while I can think of counter cases easily enough, in the large iteration is less work and less vigilance. And you cannot scale a project up without the vigilance requirement amortizing basically to 0 per line of code.
I think maybe in languages like Ruby or Smalltalk a loop can be more readable, because of how they structure it as messages to objects, rather than special keywords in the language.
This is true for some languages, but not all.
E.g. scala has @tailrec annotations, which make it a compile error for the annotated function to not be tail recursive. Clojure doesn't have tail call elimination, but has the `recur` special form for explicit recursion that is guaranteed to not consume any stack space.Rust has reserved the `become` keyword that will eventually guarantee tail call elimination (So pretty similar to Clojure's recur, but I think Rust's version will allow mutual recursion)
Zig goes the whole hog, and has `@call(modifier, fn, args)`, where `modifier` can be things like compile_time, always_tail, always_inline, never_tail, never_inline, and a bunch other desirable guarantees you might want.
What do you mean by easier to scan? I find (most) loops [0] hard to read, because they typically involve mutable state.
When properly implemented, tail calls are as fast as gotos and loops, and don't blow up any stack. (Not all languages are implemented with a stack in any case.)
However you have one point:
Most of the time, we don't use recursion directly in our programs even in a language like Haskell or Scheme. Instead we define a 'combinator' that encapsulates the specific, limited recursion scheme that we want, and then use that one. This is very similar to how people generally don't use goto directly in their programs.
You might be familiar with the combinators 'map', 'filter' and perhaps 'reduce'/'foldr'. You could re-interpret the various common loop types as such recursion combinators that weaker languages have to bake into their language, because they are not strong enough to express them as a user-defined library. And indeed, Haskell has Control.Monad.Loops (https://hackage.haskell.org/package/monad-loops-0.4.3/docs/C...) which gives you exactly the common loop types as a library.
Some examples of less common combinators are eg 'unfold' or various combinators to traverse trees or graphs.
[0] The foreach-loop over some sequence is less headache inducing than eg a while-loop.
It's well worth being familiar with both - if you learn how to shoehorn both approaches where they aren't ideal, your judgement on avoiding such practices will improve. :)
Pretty much true for any functional feature. Great in the classroom, less practical in the real world.
I have kind of grown to prefer Clojure's loop/recur construct, since it gives you something more or less akin to tail recursion but it doesn't pretend to be actually recursive.
The expectation that iterative recursion ought to have a call stack is the problem here and wouldn't be up for debate if people had done their due diligence and read their SICP.
I actually like the compromise. I get to write safe functional code while getting all the benefits of a highly optimised iterative operation.
https://pragtob.wordpress.com/2016/06/16/tail-call-optimizat...
But most of the time you will want to express your program in terms of more restricted combinators, because restriction makes the readers job easier. Easier to understand, and easier to convince yourself that no weird things are happening.
Basically, you might already agree that restricting mutation is good. This is the same principle.
So when you see a 'fold' you know even without looking at the callback, that your program will run through the whole list and not exit early. When you see a 'map' you also know that no early exit will happen, but even more you know exactly how the return value will be constructed (whereas for fold that's arbitrary).
However you are right that 'fold' and 'filter' and 'map', just like 'for' and 'while', are not good as universal building blocks.
That's why you should define new combinators when you need them. Typically, that's when you define new data structures, eg when you define a tree you will also want to define a 'map' for it, and also various tree traversals and perhaps searches. Less typically, you also want new combinators for new algorithmic ideas, even on old data structures.
Eg matrix multiplication is an interesting combinator. You provide the meaning of 'addition' and 'multiplication' as call-backs, and depending on your choice you get an algorithm for finding shortest paths or for matching regular expressions etc (in addition to the obvious matrix-multiplication on real numbers, of course). See https://news.ycombinator.com/item?id=9751987
It's relatively seldom that you want to use 'naked' recursion. The main example I can think of is when implementing state machine or interpreters. See eg https://news.ycombinator.com/item?id=43076088 for the latter, and https://news.ycombinator.com/item?id=43076088 for the former.
It is true that every tail recursive function can be converted into a semantically equivalent loop via a transformation like CPS (which the author mentions). However, for mutually tail-recursive functions, this conversion loses control flow information. This is because after the CPS transformation, calls to the other function become calls to a continuation; this call usually must be implemented as an indirect jump. On the other hand, mutually tail-recursive functions can call each other with direct/statically-known jumps.
This loss of information might appear trivial, but in practice it has some important consequences. Classic examples are interpreter loops. It is well-known that computed gotos can result in modest to large speedups for interpreters [1]. The reason why is that computed gotos create an indirect jump per opcode, so a branch predictor can take advantage of correlations between opcodes. For example, looking at Python disassembly, the header of a standard range for loop compiles down to three opcodes: GET_ITER, FOR_ITER, STORE_FAST in sequence [2]. A branch predictor can recognize that the target of the "FOR_ITER" indirect jump will likely be the "STORE_FAST" instruction pointer; it cannot predict this in the naive implementation where jumps for all instructions are "merged" into a single indirect jump / switch at the top of the loop body. In this case, computed goto is effectively equivalent to a CPS transformation whose closures require no storage on the heap.
Suppose, however, we know even more information about the instruction sequence; for example, we know ahead of time that every FOR_ITER opcode will be followed by a STORE_FAST opcode. We could completely replace the indirect jump with a direct jump to the instruction pointer for the STORE_FAST opcode. Because modern branch predictors are very good, this will have about the same performance in practice as the computed goto loop.
However, consider the limiting case where we know the entire instruction sequence beforehand. If we write our interpreter as many mutually tail-recursive functions, with one function for every instruction, an optimizing compiler can replace every indirect call with a direct (tail-recursive) call to the function that implements the next instruction's opcode. With a good enough optimizer / partial evaluator, you can turn an interpreter into a compiler! This is known as the first Futamura projection [3].
To see an example of this in action, I wrote a prototype of a Brainfuck compiler via the Futamura projection; it uses LLVM as a partial evaluator [4]. The main interesting function is `interpret`, which is templated on the program counter / instruction. That is, `interpret` is really a family of mutually tail-recursive functions which statically call each other as described above. For short Brainfuck programs, the LLVM optimizer is able to statically compute the output of the Brainfuck program. (The one in the Godbolt link compiles to a loop, likely because LLVM does not want to unroll the mutual recursion too much.) You can play around with different Brainfuck programs by modifying the `program` string on line 5.
[1] https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e...
[2] https://godbolt.org/z/rdhMvPo36
[3] https://en.wikipedia.org/wiki/Partial_evaluation#Futamura_pr...
[4]
To the contrary, I'd argue that immutability isn't the only alternative to universal mutability: many newer imperative languages (such as Rust) have various forms of controlled mutability, where one must explicitly declare which variables may be modified by imperative assignments.
IME, controlled mutability captures just about all the benefit of immutable languages, without requiring any special data structures or sufficiently-smart compiler analyses to ensure good performance. I've never really understood the desire for tail-recursive versions of iterative algorithms, except for a prior commitment to functional programming.
It is a tradeoff one can make, and it lends itself to high performance but it does come at a cost.
I don't understand why someone would want to hold on nostalgically to restrictions we no longer face.
Controlled mutability is a step up, yes. Btw, even languages like Haskell give you plenty of mutability to play with, if you want to. (Eg MVars and TVars are a thing.)
You are right that replacing a loop one for one with a tail recursive version doesn't give you much benefit either way. (Though it does make my life easier, because you don't have to contort my brain around keeping track of mutation.)
However that's a bit of a straw man and misses the broader picture.
What you'd want to do is define combinators that encapsulate the specific pattern of computation you want to implement. The most commonly known combinators are things like 'map' and 'filter'. But there are plenty more useful ones you can define, like various tree traversals or whatever makes sense for use cases and data structures.
Whether those combinators are implemented with tail calls or with loops or gotos or whatever is an implementation detail that their users don't need to worry about.
I know of one major use case where you'd want to use tail recursion directly: state machines and interpreters. See https://news.ycombinator.com/item?id=43076088 for an example of the latter. See https://en.wikisource.org/wiki/Lambda:_The_Ultimate_GOTO for an example of the former.
Tail-recursion and iteration are broadly equivalent right? So picking one over the other is a matter of style and capability.
You can't use iteration if your language isn't capable of it, but no worries, you can use tail recursion.
Similarly, you can't use tail recursion if your language isn't capable of it, but no worries, you can use iteration, at least for iterative tail recursion. Otoh, there are uses of tail call elimination that aren't recursion (or aren't direct recursion) ... that can get akward if your language can't manage it.
- V8 JavaScript Engine
- Python
Tail calls being jumps is the key insight.
Not all tail calls are recursion!
Students are confused by recursion. Some may be confused by tail calls.
Don't mix two confusing things together when teaching.
(Tail calls get mixed up with recursion because recognizing and treating/optimizing recursive tail calls to create loops an important highlighted category. In a compiler that doesn't optimize tail calls, optimizing self tail calls is an important priority (if that is easier to do than a general treatment). Many common algorithms are expressible in just one function that calls itself, and there are cases in which some or all of those calls can be tail calls; e.g. binary tree traversal.)
The order should probably be: teach recursion first. Then when students have firmly wrapped their heads around it, introduce tail calls. Students will gain the skill of knowing what is a tail call and why it is important, and recognize which calls tail calls. Secondly, the harder skill of taking recursion that uses non-tail calls and restructuring it to make tail calls instead.
However, loops aren't the only use for tail recursion. Another classic example are state machines as described in the 'Lambda: the ultimate goto' paper. See eg https://en.wikisource.org/wiki/Lambda:_The_Ultimate_GOTO
[0] Well, recursion on functions. You can also have eg recursive data types or recursion in mathematics in general. But let's focus on functions.
Loops are merely a special case of recursion. The reason languages have loops is that reifying these cases to language constructs simplifies code generation. The downside is that it muddles the logic of computation.
Enthusiasm for tail recursion comes mostly from LISP and LISP-adjacent people - those who learned to program from SICP.[1] This is neither good nor bad. Even MIT doesn't use SICP any more, though.
(The classic 20th century "programming should be hard and programmers should suffer" books:
- Structure and Interpretation of Computer Programs, Abelson and Sussman.
- Fundamental Algorithms and Semi-Numerical Algorithms, Knuth.
- Algorithms + Data Structures = Programs, Wirth.
- A discipline of programming, Dijkstra.
These are mostly of historical interest now, but at one time, knowing those defined a real computer scientist. Today, it's more important that your LLM has been trained on them.)
"Love the lambda." - footer of original article.
[1] https://archive.org/details/Sicp.2nd