What is recursion and when should I use it?

by

There are a number of good explanations of recursion in this thread, this answer is about why you shouldn’t use it in most languages.* In the majority of major imperative language implementations (i.e. every major implementation of C, C++, Basic, Python, Ruby,Java, and C#) iteration is vastly preferable to recursion.

To see why, walk through the steps that the above languages use to call a function:

  1. space is carved out on the stack for the function’s arguments and local variables
  2. the function’s arguments are copied into this new space
  3. control jumps to the function
  4. the function’s code runs
  5. the function’s result is copied into a return value
  6. the stack is rewound to its previous position
  7. control jumps back to where the function was called

Doing all of these steps takes time, usually a little bit more than it takes to iterate through a loop. However, the real problem is in step #1. When many programs start, they allocate a single chunk of memory for their stack, and when they run out of that memory (often, but not always due to recursion), the program crashes due to a stack overflow.

So in these languages recursion is slower and it makes you vulnerable to crashing. There are still some arguments for using it though. In general, code written recursively is shorter and a bit more elegant, once you know how to read it.

There is a technique that language implementers can use called tail call optimization which can eliminate some classes of stack overflow. Put succinctly: if a function’s return expression is simply the result of a function call, then you don’t need to add a new level onto the stack, you can reuse the current one for the function being called. Regrettably, few imperative language-implementations have tail-call optimization built in.

* I love recursion. My favorite static language doesn’t use loops at all, recursion is the only way to do something repeatedly. I just don’t think that recursion is generally a good idea in languages that aren’t tuned for it.

** By the way Mario, the typical name for your ArrangeString function is “join”, and I’d be surprised if your language of choice doesn’t already have an implementation of it.

More Related Contents:

  1. Way to go from recursion to iteration
  2. Solution for “Fatal error: Maximum function nesting level of ‘100’ reached, aborting!” in PHP
  3. Determining complexity for recursive functions (Big O notation)
  4. Tower of Hanoi: Recursive Algorithm
  5. Prolog Accumulators. Are they really a “different” concept?
  6. How can I make recursive templates in AngularJS when using nested objects?
  7. Is Cmake set variable recursive?
  8. Recursive function causing a stack overflow
  9. “application: not a procedure” in binary arithmetic procedures
  10. count the number of calls of a clause
  11. recursive variadic template to print out the contents of a parameter pack
  12. Recursion vs loops
  13. Real-world examples of recursion [closed]
  14. I got “scheme application not a procedure” in the last recursive calling of a function
  15. Implications of foldr vs. foldl (or foldl’)
  16. How does the fibonacci recursive function “work”?
  17. Examples of Recursive functions [closed]
  18. Is it possible to make a recursive closure in Rust?
  19. What does “Overflow evaluating the requirement” mean and how can I fix it?
  20. SICP recursive process vs iterative process: using a recursive procedure to generate an iterative process
  21. Which recursive functions cannot be rewritten using loops? [duplicate]
  22. divide a number by 2 recursively
  23. What is the difference between statically typed and dynamically typed languages?
  24. What are the differences between NP, NP-Complete and NP-Hard?
  25. Deep recursive array of directory structure in PHP
  26. python recursive vectorization with timeseries
  27. Permutation algorithm without recursion? Java
  28. Generate permutations of JavaScript array [duplicate]
  29. Using Haskell’s map function to calculate the sum of a list
  30. BASH: Writing a Script to Recursively Travel a Directory of N Levels

Leave a Comment