Menu
I am familiar with the general awareness around recursion - don't use it as it is not a good memory management practice. However, that concept should be applied to all the programming languages unless they handle the memory management under recursion really well.
While going through a documentation from Educative's Rust course, there was a statement made:
Recursion is possible in Rust, but it’s not really encouraged. Instead, Rust favors something called iteration, also known as looping.
I am unable to grasp why is this the case? Is there something not-so-common in Rust as compared to other languages that recursion is not suggested or iteration is handled better in Rust than in other languages?
574
The Bad. In imperative programming languages, recursive functions should be avoided in most cases (please, no hate mail about how this isn't true 100% of the time). Recursive functions are less efficient than their iterative counterparts. Additionally, they are subject to the perils of stack overflows.
There is only one problem: Rust does not do any tail call optimization (yet). Now, the crate tramp does its job. We implemented in this crate a trampoline. A trampoline simulates a tail call optimization by calling a function which might return another function (which will be called again) or a computed result.
Yes, recursion can be used in production code with some defensive coding practices.
Recursion is never technically necessary. One can always use a loop. In many circumstances, recursion will be a disadvantage, as it will require maintaining activation records on the stack that would not be required with an iterative solution.
I am unable to grasp why is this the case? Is there something not-so-common in Rust as compared to other languages that recursion is not suggested or iteration is handled better in Rust than in other languages?
Most languages very much "prefer" iteration to recursion, they just don't bother spelling it out so explicitly. For instance, Python has an interpreter-level limit on recursion depth with a measly default of 1000.
This might be explicitly noted for Rust because its origin lies in part in functional languages which are basically the only ones favoring recursion: many constructs are inspired by MLs and Haskell and the initial compiler was in OCaml, which I don't think even has a construct for iteration (a.k.a. any sort of for or while loop).
As to why a language would favor iteration, and disfavor recursion: without Tail Call Elimination (TCE), recursion will cause consumption of stack space, possibly unbounded.
If the language uses the C stack and unless it also sets its own recursion limit, it has no way to easily know how deep the stack can be: the defaults can be as high as 8MB on Linux (glibc really) and as low as 64k for OpenBSD (at least in the days of OpenBSD 4), with very few ways to query this information, and no real way to cleanly check it (plus the check would not be free either way). More problematically, a stack overflow will at best segfault (hard-crashing the program) and at worse cause memory unsafety, so that's something you really want to avoid.
Even without that — and again assuming you don't have TCE — an unbounded loop implemented recursively (e.g. an event loop) will consume an unbounded amount of memory, because each recursive call will reserve a stack frame which will never be reclaimed as the function never returns.
An infinite iterative loop may burn 100% of your CPU all the same (if you're not doing anything which waits on an IO event or a lock) but will not eat all your memory unless you specifically and explicitly accumulate data (e.g. push stuff into a vector).
If you do have TCE, then technically you don't need iteration at all and there are in fact many languages which don't bother with it. To my knowledge, OCaml and Erlang (this is not at all an exhaustive list but these two I'm reasonably certain of) don't have any sort of loop construct, as long as your recursive call is in tail position it will be optimised away.
That latter bit is what makes it slightly more complicated, and easy to get wrong: for TCE to work, the call has to be in tail position, meaning the very last thing you do: foo() is a tail call, but 1 + foo() is not, the addition is in tail position instead of the call. This means it's easy to make a function non-tail-recursive by mistake, and you often need to materialise your loop as an ancillary accumulator-based function to resolve the issue (e.g. in the case above instead of 1 + foo() you'd call foo2(1) and it would perform the increment internally, something like that). The language designers and implementors need to specify and implement TCE, which takes some efforts, can limit your options, etc...
Finally, in the answer I talk specifically about tail call elimination (TCE). You may have heard of tail call optimization (TCO), which Rust has because its backend is LLVM which has TCO.
The problem of TCO is that optimisation implies heuristics and an element of chance: the compiler may or may not optimise a recursion depending on call kind, function size, number (and size) of arguments, control flow, etc..., and the optimisation may not even be implemented on all backends. This means TCO can't be the basis for language semantics if you're going to make your language work without an iterative construct you need tail call to be reliably removed when they appear. Hence you need tail call elimination rather than mere optimisation.
87
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
