"Recursion is fine [for your use-case]."

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

=)

If you're going to make a generalization, I think recursion is fine, efficient, and rarely dangerous.

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.

For many reasons, people often add nesting limits in recursive structures to at least constrain how bad they behave when something eventually does go wrong.

Parsers are far from immune to these issues.

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

For a fun time, make a nested json blob about 1000 layers deep[1] and in python:

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

If you parse arbitrary json bytes from the Internet (for example, if you have some public Python API with no auth) then you have given the world a fun little stacktrace generator, and a way to lessen your server room's heating bill.

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

Parsing untrusted input on a machine where failure could affect someone other than the person who provided the input is definitely a known case to be mindful of.

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.)

Yes, unfortunately in the python case the standard library's json parser has no way to configure a reasonable limit. It'll just consume stack frames until it hits the interpeter's recursion limit. And, as has been mentioned elsewhere, python stack frames are expensive for a variety of reasons.

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...

You mean like the reply depth limit in forums like YC.

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

I want to respect your beliefs. =)

In general, most json/bson parsers like libbson have a rather shallow depth restriction (xerces also constrains this if I recall.)

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

There’s an easy way to figure out if recursion is fine for your usecase

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

This code terminates only if all child-problems eventually are found not to have subproblems. So either it has infinite subproblems or it returns true. So recursion is good for a use case unless the problem decomposes into infinite subproblems, but in that case this test function never returns false.

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

"kernel: Out of memory: Kill process 9163 (Insulin-pump-task) score 511 or sacrifice child"

There are safer hobbies available like snake juggling =)