I currently have open in my editor a code formatter that I maintain that uses at least half a dozen recursive algorithms to traverse syntax trees and other data structures. This program is used by almost every user of our language, invoked on every save, and probably executed billions of times a day.

Recursion is fine.

In general it is naive, often dangerous, and an inefficient space/time trade-off.

I have been writing software for several decades... does that make one less insightful or more biased?

https://youtu.be/pmu5sRIizdw?feature=shared&t=31

=)

There may be use cases where it's insecure or has performance concerns, but those are the exception. Most of the time, it's fine.

We don't generally tell programmers that loops are naive, often dangerous, and risk locking up the program. They certainly can, but most just... don't.

Just like loops, recursion can make code much simpler to write, read, and maintain. Every modern language under the sun supports it for very good reasons. Use it.

Parsers are far from immune to these issues.

I think we will have to "agree to disagree" here... =)

  with open('lulz.json') as ayy_lmao:
      oops = json.load(ayy_lmao)

EDIT: btw you can do the same thing in rust's serde_json if the type you're deserializing into somehow supports the nesting, but you'd have to work for it.

EDIT2: the only (decent) way I can think to mitigate this in the python app's case is to enforce a sufficiently restrictive Content-Length at the edge, which obviously isn't possible of you expect blobs O(100Kb) uncompressed. Or you could pre-parse to detect nesting.

[1] EDIT3: on my machine in ipython right now it's 1485:

  import json

  def nest(d):
      return '{"k":' + str(d) + '}'

  def make_mess(n):
      v = 1
      for _ in range(n):
          v = nest(v)
      return v

  json.loads(make_mess(1485))  # boom

You'll want to cap the maximum allowed nesting depth. Even if not using recursion, you probably don't want untrusted input to be able to make your stack data structure allocate arbitrary amounts of memory.

If you do put a nesting limit in, you can do that equally well using an actual stack or recursion. (For example, I believe v8 still uses recursive descent for parsing JSON and JavaScript. It detects and handles stack overflows to ensure that untrusted input can't blow the stack and crash. I'm not sure if it's using a hardcoded nesting limit or actually trapping the stack/heap collision somehow.)

I've run into similar issues with recursive code in java. The story gets better in C or rust, but there wre still sharp edges. I guess there are sharp edges everywhere though...

Shouldn't you stick to a depth-first branch reply limit until moving to the next fork.

I want to respect your beliefs. =)

And yeah, recursion is avoided in some shops for good reasons.

   def isRecursionOk(problem)
       for (subProblem in (breakDownIntoSubProblems(problem))
           if ! isRecursionOk(subProblem) return false
       return true

Makes more sense to do it as breadth-first with only one return value:

   from collections import deque
   def isRecursionOk(problem):
       q = deque(problem)
       while q:
           problem = q.popleft()
           q.append(list(breakDownIntoSubProblems(problem)))
       return true

There are safer hobbies available like snake juggling =)

If you have a binary tree with 1 billion elements, the depth will be 20. In a b-tree with a reasonable node width (eg 16), assuming 50% occupancy the depth will be about 8.

This is, in practice, totally fine. You won't exhaust your stack traversing a balanced tree.

Of course you can, if you wanted to, just like you can control the iteration count of a loop. It's not even hard. This is simply a non-issue.

Some algorithms are much more naturally expressed recursively and writing the imperative equivalent with manual stack handling is just annoying. Stack growth is just something you don't have to worry about for almost all scenarios you're likely to encounter.

Well, it's about the tradeoffs right? If I have a recursive algorithm that's growing the stack (assuming no TCO, because few languages people actually use in production support it) I'm trading execution time, space, and reliability for economy of expression. In reverse order:

- reliability: if, as you suggest, I implement some hard depth limit (which is necessary because all the processes which are running concurrently need to not exceed my max stack depth), and assuming generally that things grow over time (more users, more concurrent processes, more recursive calls needed to get the job done) we face two issues. (1) theres a complicated relationship between the maximum number of concurrent processes and the maximum allowable recursion depth. Getting it wrong could crash the entire program! If this is a web server that's means we just killed a whole bunch of connections all at once. (2) eventually, over time, we'll need to raise the recursion limit, which entails rebalancing the concurrency limit. Hard walls like this are bad news in systems. If instead this was implemented iteratively the system would degrade softly as the iteration count grows--each process would take longer to complete, but they'd still all complete. Assuming I'm monitoring process execution time I can predict and respond to this proactively instead of being faced with an emergency where the system is just completely broken.

- space: this is obvious I guess, more stack frames == more memory. The problem is worse in some languages than others.

- time: this may be less obvious, and there may be optimizations which render it false, but generally in my experience iterative code gets pipelined better and runs quicker.

> Stack growth is just something you don't have to worry about for almost all scenarios you're likely to encounter.

I guess that depends on the situation. I've encountered hard walls and performance issues from recursion enough times in my career thus far that I make the extra effort to avoid it. I could totally see the value, though, in areas where you know ahead of time how the recursion depth will scale over time. More often than not, though, that's unknowable at implementation time so better err on the side of caution.

EDIT: upon re-reading this I think it might have been clearer if I insted wrote "task" every time I wrote "process"--I'm not talking specifically about any OS feature.

My process for deciding when to use iteration or recursion is simple: if each step needs to keep context then use recursion, otherwise use iteration (unless recursion with TCO is the native idiom of course).

I've never had an issue that wasn't an obvious bug that iteration would have somehow solved. If any bug that terminated a thread was fatal to the whole process then I suggest the thread termination handler should handle this more gracefully.

Increased space usage is a non-issue IMO. Translating a stack frame to a data structure you manage as an explicit stack requires the same space within a small constant factor.

And an oft-ignored factor is the cleanup advantages of allocating on the stack, which offsets any space and time disadvantages you might see with recursion.

Quite likely :)

> And an oft-ignored factor is the cleanup advantages of allocating on the stack, which offsets any space and time disadvantages you might see with recursion.

This is a very good point.

Alright, you've convinced me to start playing with recursion again. Just not in java or python.

So, if you try to unroll naive recursive code, than one wins n-many issues instead of 1 predictably separable one. Sure one could pass in a mutex etc., but it is back to using a global again and a single-core bounded context.

Best of luck, =)

An easy way to do it is to just pass a separate "depth" integer parameter into the recursive function. It then passes that +1 when it makes a recursive call. At the top of the function, if the depth is above your chosen limit, you bail out in some way instead of continuing to recurse.

> you detect that situation and make it work.

If you really do need to "make it work" for arbitrarily-deeply nested inputs, then you are actually better off using a heap-allocated stack instead of recursion.

But in most cases, a recursive implementation will only exceed the stack if the input is malicious or pathological and you can just fail in that case.

I didn't actually say that, but even supposing I meant that, walking a 3D mesh in a way that requires you to keep stack context sounds like a pretty unlikely/niche scenario, so it seems even that stronger statement is true.

It's fairly intuitive to walk a mesh recursively by following adjacent edges and you have to keep track of where you've been which means storing a lot of data somewhere. Maybe there are better algorithms but sometimes you just reach for what's most obvious. I suppose there are many analogous applications of traversing a graph structure.