Is recursion better than loops in programming

Recursion or while loops


I've read about some development interview practices, particularly the technical questions and tests asked during the interviews, and I've stumbled upon sayings of the genre a couple of times. "Ok, you solved the problem with a while loop, now you can do recursion" or "Anyone can do this with a 100 line while loop, but can they do this with a 5 line recursion function? "etc.

My question is, in general, is recursion better than if / during / for constructs?

In all honesty, I've always thought that recursion was not to be preferred because it is limited to the stack, which is much smaller than the heap. Also, executing a large number of function / method calls is not optimal from a performance standpoint, but I can be wrong ...






Reply:


In and of itself, recursion is no better or worse than loops - each has advantages and disadvantages, and these even depend on the programming language (and implementation).

Technically, iterative loops are a better fit with typical hardware-level computer systems: at the machine code level, a loop is just a test and a conditional jump, while recursion (naively implemented) involves moving a stack frame that involves jumping, returning, and jumping back from the stack. OTOH, many cases of recursion (especially those trivially equivalent to iterative loops) can be written so that the stack push / pop can be avoided; It can do this if the recursive function call is the last event in the function body before it is returned. This is commonly called the Tail call optimization (or Tail recursion optimization ) designated. A properly tail-call-optimized recursive function is mostly like an iterative loop at the machine code level.

Another consideration is that iterative loops require destructive state updates that make them incompatible with pure (side-effect-free) language semantics. This is why pure languages ​​like Haskell have no loop constructs at all, and many other functional programming languages ​​either do not avoid them entirely or avoid them as much as possible.

The reason these questions are so common in interviews is that in order to answer many important programming concepts - variables, function calls, scopes, and of course loops and recursions - you need to thoroughly understand the mental flexibility that allows you to address a problem from two radically different angles and switch between different manifestations of the same concept.

Experience and research suggest that there is a boundary between people who can understand variables, pointers, and recursions and those who cannot. Almost everything else in programming, including frameworks, APIs, programming languages ​​and their constraints, can be obtained through study and experience. However, if you cannot develop an intuition about these three core concepts, you will not be able to be a programmer. Translating a simple iterative loop into a recursive version is the fastest way to filter out non-programmers. Even an inexperienced programmer can usually do this in 15 minutes, and it is a very language-independent problem that the candidate can choose a language of their choice rather than stumbling over idiosyncrasies.

If you get a question like this in an interview, it is a good sign: the prospect is looking for people who can code, not people who have memorized a programming tool manual.







It depends on.

  • Some problems are very prone to recursive solutions, such as: B. Quicksort
  • Some languages ​​do not support recursion, e.g. early FORTRANs
  • Some languages ​​adopt recursion as the primary means of grinding, e.g. B. Haskell

It's also worth noting that the tail recursion support equates the recursive and iterative loops of the tail. That said, recursion doesn't always have to waste the stack.

A recursive algorithm can also always be implemented iteratively using an explicit stack.

Finally, I'd note that a five line solution is probably always better than a 100 line solution (assuming they are actually equivalent).







There isn't a generally accepted definition of "better" when it comes to programming, but I take it as "easier to maintain / read".

Recursion is more expressive than iterative loop constructs: I say this because a while loop is like a recursive tail function, and recursive functions don't have to be recursive. Powerful constructs are usually a bad thing because they allow you to do things that are difficult to read. However, recursion gives you the ability to write loops without using mutability, and in my opinion mutability is much more powerful than recursion.

From low expressiveness to high expressiveness, loop constructs stack up as follows:

  • Recursive functions that use immutable data,
  • Recursive functions that use immutable data,
  • While loops that use mutable data
  • Tail recursive functions that use mutable data,
  • Recursive functions that use mutable data,

Ideally, you'd use the least descriptive constructs you can. If your language does not support tail call optimization, this can of course also influence your choice of the loop construct.







Recursion is often less obvious. Less obvious is harder to maintain.

When you write in the main flow, make it clear that you are writing a loop. When you write, you are not really making it clear what is going to happen. See content only: This call indicates that this is actually a loop using iterations. Also, you can't just place an escape condition somewhere in the middle of the iterations. You either need to add a condition that will be returned all the way or throw an exception. (And exceptions make it even more complicated ...)

Essentially, when there is an obvious choice between iteration and recursion, do the intuitive thing. If iteration easily does the job, then storing 2 rows is rarely worth it in the long run.

Of course, if you save 98 lines, that's another matter entirely.

There are situations for which recursion is just perfect and which are not really unusual. Traversing tree structures, multi-linked networks, structures that may contain their own type, multidimensional jagged arrays, essentially anything that is neither a simple vector nor an array of fixed dimensions. When you are traversing a known, straight path, you iterate. If you dive into the unknown, grab it.

Basically, you should forget about iterations if you want to call more than once per level on your own.

... Iterative writing of functions for tasks that are best done by recursion is possible, but not pleasant. Wherever you want, you need something like. I did it once, more as an exercise than for practical purposes. I can assure you that once you face such a task, as you put it, you will have no more doubts.







As usual, there is generally no answer to this, as there are additional factors which in practice are largely unequal between the cases and unequal within a use case. Here are some of the pressures.

  • Short, elegant code is generally superior to long, complex code.
  • However, the last point is somewhat invalid if your developer base is unfamiliar with recursion and unwilling / unable to learn. It can even be an easy one negative be considered a positive.
  • The recursion can be bad for efficiency, if You need heavily nested calls in practice and cannot use tail recursion (or if Your environment cannot optimize tail recursion).
  • In many cases, recursion is bad even if you cannot cache intermediate results properly. For example, the common example of using tree recursion to compute Fibonacci numbers is terrible bad if you don't cache. When you cache, it's easy, quick, elegant, and overall wonderful.
  • Recursion is not applicable in some cases, just as iteration is in others and absolutely necessary in other cases. Traversing long chains of business rules is usually not supported by recursion at all. Iterating through data streams can be carried out sensibly with recursion. Iterating over multidimensional dynamic data structures (e.g. labyrinths, object trees ...) is practically impossible without recursion, explicitly or implicitly. Note that in these cases the explicit recursion much is better than the implicit - nothing is more painful than reading code with someone implementing their own incomplete, flawed ad hoc batch within the language to avoid the creepy R-word.







It really comes down to convenience or requirement:

If you are using the Python programming language, recursion is supported. By default, however, the recursion depth is limited to 1000. If it exceeds the limit we will get an error or an exception. This limit can be changed, but if we do, abnormal situations in the language can arise.

At this point (number of calls more than recursion depth) we have to give preference to loop constructs. I mean, if the stack size is insufficient, we have to give preference to the loop constructs.



Use the strategy design pattern.

  • Recursion is clean
  • Loops are (arguably) efficient

Choose one based on your exposure (and / or other conditions).






We use cookies and other tracking technologies to improve your browsing experience on our website, to show you personalized content and targeted ads, to analyze our website traffic, and to understand where our visitors are coming from.

By continuing, you consent to our use of cookies and other tracking technologies and affirm you're at least 16 years old or have consent from a parent or guardian.

You can read details in our Cookie policy and Privacy policy.