Is recursion ever faster than looping?

by

This depends on the language being used. You wrote ‘language-agnostic’, so I’ll give some examples.

In Java, C, and Python, recursion is fairly expensive compared to iteration (in general) because it requires the allocation of a new stack frame. In some C compilers, one can use a compiler flag to eliminate this overhead, which transforms certain types of recursion (actually, certain types of tail calls) into jumps instead of function calls.

In functional programming language implementations, sometimes, iteration can be very expensive and recursion can be very cheap. In many, recursion is transformed into a simple jump, but changing the loop variable (which is mutable) sometimes requires some relatively heavy operations, especially on implementations which support multiple threads of execution. Mutation is expensive in some of these environments because of the interaction between the mutator and the garbage collector, if both might be running at the same time.

I know that in some Scheme implementations, recursion will generally be faster than looping.

In short, the answer depends on the code and the implementation. Use whatever style you prefer. If you’re using a functional language, recursion might be faster. If you’re using an imperative language, iteration is probably faster. In some environments, both methods will result in the same assembly being generated (put that in your pipe and smoke it).

Addendum: In some environments, the best alternative is neither recursion nor iteration but instead higher order functions. These include “map”, “filter”, and “reduce” (which is also called “fold”). Not only are these the preferred style, not only are they often cleaner, but in some environments these functions are the first (or only) to get a boost from automatic parallelization — so they can be significantly faster than either iteration or recursion. Data Parallel Haskell is an example of such an environment.

List comprehensions are another alternative, but these are usually just syntactic sugar for iteration, recursion, or higher order functions.

More Related Contents:

  1. Why should recursion be preferred over iteration?
  2. What is the fastest and pythonic way to generate a list [(0,0), (0,1), (0,2)…(0,100)]? [closed]
  3. Why are loops always compiled into “do…while” style (tail jump)?
  4. Speed up the loop operation in R
  5. Recursion or Iteration?
  6. Is a Recursive-Iterative Method Better than a Purely Iterative Method to find out if a number is prime?
  7. How can I call a macro which contains a loop but only run one iteration of that loop?
  8. High-performance merging of ordered sets
  9. Google app script timeout ~ 5 minutes?
  10. What is the best approach to encapsulate blocking I/O in future-rs?
  11. Why does breaking the “output dependency” of LZCNT matter?
  12. nth fibonacci number in sublinear time
  13. Create group number for contiguous runs of equal values
  14. Timing JavaFX Canvas Application
  15. What’s the fastest way to merge/join data.frames in R?
  16. Recursion vs loops
  17. How to optimize vlookup for high search count ? (alternatives to VLOOKUP)
  18. What is the fastest way to get the value of π?
  19. Fast query runs slow in SSRS
  20. Entity Framework query slow, but same SQL in SqlQuery is fast
  21. Bulk inserts taking longer than expected using Dapper
  22. Why are compilers so stupid?
  23. SVN performance after many revisions
  24. In SQLite, do prepared statements really improve performance?
  25. Why is appending to a list bad?
  26. Why is putImageData so slow?
  27. Client-side logic OR Server-side logic?
  28. Trouble converting long list of data.frames (~1 million) to single data.frame using do.call and ldply
  29. Projecting a list of lists efficiently in F#
  30. MongoDB’s performance on aggregation queries

Leave a Comment