25

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?

Aviral Srivastava
  • 4,058
  • 8
  • 29
  • 81
  • 4
    Not so much Rust specific, but recursion builds on the stack which could lead to stack overflow, while an iterative solution won't. You can guard yourself against not being able to allocate memory, but not for being short on stack memory. I also think that tail optimization isn't implemented in Rust, but it is on the agenda (or might already have been implemented). – Ted Klein Bergman Jan 29 '21 at 04:00
  • a minor reason: https://stackoverflow.com/a/39840726/5581893 – Dee Jan 29 '21 at 04:00
  • Isn't iteration preferred over recursion (whenever possible) in every languages? Nothing surprising about that. – user202729 Jan 29 '21 at 05:20
  • 1
    @user202729 languages with TCE (not to be confused with TCO) are perfectly happy with recursion. They may not even have imperative iteration (see e.g. Erlang). – Masklinn Jan 29 '21 at 06:36
  • @Masklinn ... ah yes, then in C-family languages. – user202729 Jan 29 '21 at 06:40
  • A couple of other considerations. Recursion may be faster than an iterative alternative that requires heap allocation. Building an iterative function (i.e. a loop) makes it easier to convert to a rust iterator (i.e. store all state in a struct and implement Iterator) which in turn makes it easier to support async execution (call the iterator to progress the function). In rust, iteration may also help avoid explicitly defining lifetimes which may be introduced with recursion if you're passing & returning references. – optevo Jun 30 '22 at 06:07

1 Answers1

42

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.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
Masklinn
  • 34,759
  • 3
  • 38
  • 57
  • 2
    [When is tail recursion guaranteed in Rust?](https://stackoverflow.com/q/59257543/155423) – Shepmaster Aug 03 '21 at 13:41
  • 4
    Just FYI, OCaml does indeed have constructs for iteration. Both `for` and `while` loops are possible in OCaml. Here is a one-liner example of a `for` loop: `for i = 0 to 3 do printf "i = %d\n" i done;;`. – Austin Davis Feb 26 '22 at 09:25
  • 1
    I get why in safety-critical situations, you want to protect the stack. But I find the oft-repeated recommendation to avoid recursion gets propagated as *never* use recursion. There are many problems where recursion depth is limited to the log of the length of the input sequences, so typically 64 is the maximum possible. Writing the state and jump, etc. to emulate recursion can also be error prone. Better advise is to always stop and think when you see recursion as a possible solution. – THK Feb 24 '23 at 17:00