4 ms·

It's interesting to use languages that do not harshly penalize recursion by imposing stack size limits. The upcoming GNU Guile 2.2 release, a Scheme implementa

It's interesting to use languages that do not harshly penalize recursion by imposing stack size limits. The upcoming GNU Guile 2.2 release, a Scheme implementation, has a dynamically expandable stack so algorithms that are naturally recursive can be implemented that way rather than contorted into iterative form to please the stack limit god. For example, in Guile 2.0, this natural definition of 'map' will cause the stack to overflow on large lists: (define (map proc lst) (if (null? lst) '() (cons (proc (car lst)) (map proc (cdr lst))))) The iterative solution is to construct the list backwards and reverse it as a final step: (define (map proc lst) (let loop ((lst lst) (result '())) (if (null? lst) (reverse result) (loop (cdr lst) (cons (proc (car lst)) result))))) There's no real gain here in terms of performance or readability. You trade a large stack for a large reverse operation at the end. Guile 2.2 allows a whole class of recursive algorithms that were not practical before because of the fixed size stack (like most languages I know of), and they perform well, too! Needless to say I agree with this article. Recursion is an integral part of computing, and more programming languages should provide better support for it. Embrace it, don't avoid it!

Jtsummers 11y ago
There is a performance gain. Two primary gains: reduced memory usage (your stack size is constant, with tail-call elimination); theoretically faster execution as you don't have a cons and a return pending at the end of each iteration. You also eliminate the function call, potentially, on the recursive call. If TCE is present, instead of a function call, the recursive step is actually just a branch (and can be an unconditional branch in many cases). Reverse can also be made efficient, as the Erlang people have done. I will agree that the first version is clearer in illustrating the intent of the program for many people. The second one is probably just familiar for me from my time playing with Erlang, where it's the idiomatic way to write something like this.
AnimalMuppet 11y ago
But can you do that with something like fibonacci? You can't just tail-call optimize that away, can you, since there are two recursive calls?
- chriswarbo 11y ago
  I was under the impression that Schemes generally compile down to continuation-passing-style, and hence in the case of something like Fibonacci one of the recursive calls would be performed as a tail call, whilst the other would become part of the continuation, e.g. something like: function fib(n, k) { if (n == 0) k(1); if (n == 1) k(1); fib(n-1, function(f_1) { fib(n-2, function(f_2) { k(f_1 + f_2); }); }); }
- davexunit 11y ago
  The natural recursive definition of a Fibonacci function is a different beast. The big issue with the naive and simple Fibonacci implementation is that it duplicates work, a ton of it. The 'map' above doesn't have this issue. To make Fibonacci efficient, it can be implemented as an iterative algorithm which isn't too bad to read. But there's better news! The recursive algorithm can be kept as-is, provided that the function is memoized, so that already computed values are cached.

Jtsummers 11y ago

There is a performance gain. Two primary gains: reduced memory usage (your stack size is constant, with tail-call elimination); theoretically faster execution as you don't have a cons and a return pending at the end of each iteration. You also eliminate the function call, potentially, on the recursive call. If TCE is present, instead of a function call, the recursive step is actually just a branch (and can be an unconditional branch in many cases). Reverse can also be made efficient, as the Erlang people have done. I will agree that the first version is clearer in illustrating the intent of the program for many people. The second one is probably just familiar for me from my time playing with Erlang, where it's the idiomatic way to write something like this.

AnimalMuppet 11y ago

But can you do that with something like fibonacci? You can't just tail-call optimize that away, can you, since there are two recursive calls?

chriswarbo 11y ago
I was under the impression that Schemes generally compile down to continuation-passing-style, and hence in the case of something like Fibonacci one of the recursive calls would be performed as a tail call, whilst the other would become part of the continuation, e.g. something like: function fib(n, k) { if (n == 0) k(1); if (n == 1) k(1); fib(n-1, function(f_1) { fib(n-2, function(f_2) { k(f_1 + f_2); }); }); }
davexunit 11y ago
The natural recursive definition of a Fibonacci function is a different beast. The big issue with the naive and simple Fibonacci implementation is that it duplicates work, a ton of it. The 'map' above doesn't have this issue. To make Fibonacci efficient, it can be implemented as an iterative algorithm which isn't too bad to read. But there's better news! The recursive algorithm can be kept as-is, provided that the function is memoized, so that already computed values are cached.