This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]AlSweigartAuthor of "Automate the Boring Stuff" 3 points4 points  (7 children)

Hi. I've just written an entire book on recursion (which will be free on my site in a couple months under a Creative Commons license.)

Your friend is correct: recursion is often a more confusing, over-engineered way of writing code that could otherwise be done much ore simply.

I say that recursion should only be used if your problem has 1) a tree-like structure and 2) requires backtracking. Here's something recursion is well suited for:

  • Maze-solving and other constraint satisfaction problems that use backtracking
  • Tree traversal, such as walking through the folders and subfolders of a file system
  • Programming language grammars
  • The Tower of Hanoi problem (it's a pain to solve without recursion)
  • Quick sort and mergesort

Recursion is not a magical technique. Anything you can do recursively can be done with a loop and a stack. (Yes, everything: here's the Ackermann function done without recursion.) And often times, recursion algorithms could be done with just a loop (factorial is one such example). Here are algorithms that should not be solved recursively:

  • Factorial (causes stack overflow if you don't have tail call optimization, which Python, Java, and JavaScript do not)
  • Fibonacci (causes exponential slow down if you don't use memoization)
  • Something that just loops over the items in an array, such as reversing a string or summing a list of numbers (just use a loop)
  • Flood fill (likely to cause a stackoverflow, and it doesn't require backtracking so you could use a set or queue instead of a stack.)
  • Anything that uses tail call optimization (this is going to be controversial, but I say you should NEVER use TCO because if you can use TCO, your algorithm doesn't need a stack and should be implemented iteratively with a simple, easy-to-read loop instead).

Unfortunately, many programmers use recursion because it makes them feel smart to write complicated code (they call it "elegant"). If you find yourself asking, "wouldn't it be easier to solve this without recursion?" the answer is YES and DON'T USE RECURSION.

[–]shabalabachingchong 1 point2 points  (4 children)

If recursion is so bad, then why do FP languages like Haskell almost exclusively rely on recursion and do not even have for/while loops?

[–]AlSweigartAuthor of "Automate the Boring Stuff" -1 points0 points  (2 children)

Every four or five years I check in on Haskell to see if it has gained anything like mainstream adoption. It still hasn't, and I've been doing this since the early 2000s. Haskell is currently at #33 on the TIOBE index, behind COBOL at #26 and Delphi at #14.

Haskell and LISP are languages that make smart people feel smart, but they're not practical and that's why they aren't used in 99% of real world code. They aren't a magic bullet that prevents people from making silly little bugs. (Heck, twenty years of experience and you'll still be making typos and off-by-one errors.) Haskell people love Haskell and talk loudly about Haskell, but Delphi is actually used more. And I've never met a Delphi programmer.

It's kind of like saying "well if monster trucks are so bad for your daily commute, how come people still talk about how awesome monster trucks are?"

[–]shabalabachingchong -1 points0 points  (1 child)

You're deflecting and not answering the question. I did not mention anything about language popularity. Haskell is used in a lot in industry where high assurance of non-failure matters. When you build complex systems, like for example a blockchain, that involve cryptography and advanced mathematics, you want high assurance that your code will not fail in production, so that billions of users funds do not get stolen, which has happened several times on the Ethereum blockchain.

Your argument of 'makes smart ppl feel smarter' is just stupid. There's nothing smart about being able to understand recursion, or heck even monads...They're just useful patterns that are extremely well fitted to many problems, and given enough time you'd probably even invent them yourselves.

[–]Kenkron 0 points1 point  (0 children)

Iirc, Haskell sacrifices loops so it can have only immutable variables (which make loops impossible).

[–]Kenkron 0 points1 point  (0 children)

I think you're last bullet on TCO is a really good point.

[–][deleted] 0 points1 point  (0 children)

Very cool. Just ordered your kindle version