5 ms·

Recursive Problems Benefit from Recursive Solutions

48 points by luispa 7mo ago

swiftcoder 7mo ago
This has always felt like the kind of thing we could be building compilers to solve. Recursive -> explicit stack is a very mechanical conversion, why can't we write a compiler transform pass that does that rewrite any time it detects a high potential for stack overflow?
- Jaxan 7mo ago
  Many compilers do change a recursion into a loop, avoiding the stack altogether!
- Epa095 7mo ago
  Yeah, tail call elimination, is definitely doable. Python famously does not have it because "Language inventor Guido van Rossum contended that stack traces are altered by tail-call elimination making debugging harder, and preferred that programmers use explicit iteration instead". https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call
- derriz 7mo ago
  It’s called TCO - tail call optimization - and gcc and llvm are supposed to implement it although tail recursive style code is probably uncommon in C or C++. Outside of that it’s common in functional languages where recursive functions are obviously idiomatic and so it has more potential to provide performance benefit. It’s not a purely local optimization - affecting the call structure so debugging is a pain point. Which is probably why most imperative language compilers don’t bother given the lack of utility for the vast majority of code bases. It feels like something that would need to be specified at the language spec or semantics level to make it useful rather than just making it optional for the compiler - otherwise the developer is probably just going to do the transform manually - to be safe - if stack explosion was a possibility if the compiler decided on a whim to not perform TCO.
  - afiori 7mo ago
    Just like many languages have annotations for inlining functions they could have annotations for tco. From an usability pov i would like annotations for must, must not, should, and should not. Where the "must" versions error if the compiler can't do the optimization
    - a57721 7mo ago
      Scala and Kotlin have 'tailrec' annotation/modifier, though not as sophisticated as you describe.
  - ufo 7mo ago
    Tail call optimization optimizes the situations where the recursion doesn't actually need any stack space, but I think the parent poster is asking about situations that aren't tail recirsive.
- ufo 7mo ago
  It's indeed very mechanical and some programming languages can do it for you. I think you're mainly asking for heap-allocated stacks. Some languages always use the heap for stack frames instead of the native stack and can set the stack limit as high as there's memory available. You might also want to look into stackful coroutines, which allow one to pause the execution of a recursive function and switch to another function. This can provide you with multiple call stacks, which is another reason people sometimes choose to use write explicit stacks.
jonathanlydall 7mo ago
It depends on whether the limited call stack capacity will be an issue for the particular problem you’re solving. I’m presently working on a problem which uses traversal of TypeScript file syntax trees. I can reasonably assume that we will never get a file with a deep enough syntax tree which would cause a stack overflow. A manually managed stack might seem safer, but as pointed out by this article the code would be more complicated and, in my case, for no good reason.
- layer8 7mo ago
  In practice, a heap-based manual stack can be as unsafe with unbounded input as using the native call stack (considering typical OOM behavior). If you have untrusted input, you might want to limit the stack depth in either case. And it’s not difficult to add a recursion counter to recursive calls. So I don’t think it’s an inherently distinguishing feature between the two approaches. Personally I tend to find the iterative approach easier to follow when no actual stack is needed, i.e. in the tail-call case.
- randomNumber7 7mo ago
  > I can reasonably assume that we will never get a file with a deep enough syntax tree which would cause a stack overflow. What if eve constructs a file specifically so that you get stack overflow?
  - jonathanlydall 7mo ago
    Eve will then experience a stack overflow exception on our app running on her PC, no doubt she will be very impressed with her achievement.
    - randomNumber7 7mo ago
      Ok, but then your argumentation is only valid for programming languages with build in saftey guards. In low level languages this would be a recipe for disaster.
- aleph_minus_one 7mo ago
twic 7mo ago
> It seems to be common knowledge that any recursive function can be transformed into an iterative function. Huh. Where i work, the main problem is that everyone is hell-bent on transforming every iterative function into a recursive function. If i had a pound for every recursive function called "loop" in the codebase, i could retire.
- skeeter2020 7mo ago
  My experience has gone the other way: lots of code with recursion, rewritten to be iterative. There really aren't that many use-cases in vanilla enterprise code that benefit from recursion when the entire cost is considered.
- adafactor 7mo ago
  Where on earth do you work? This is unusual...
twic 7mo ago
> This solution looks extremely similar to the previous one, which is a good thing. Our requirements have experienced a small change (reversing the traversal order) and our solution has responded with a small modification. Now do breadth-first traversal. With the iterative approach, you just replace the stack with a queue. With the recursive approach, you have to make radical changes. You can make either approach look natural and elegant if you pick the right example.
- aleph_minus_one 7mo ago
  > Now do breadth-first traversal. With the iterative approach, you just replace the stack with a queue. With the recursive approach, you have to make radical changes. The reason is that no programming language that is in widespread use has first-class support for co-recursion. In a (fictional) programming language that has this support, this is just a change from a recursive call to a co-recursive call.
  - Chinjut 7mo ago
    Haskell (I realize this may not pass your threshold for widespread use) has equal support for co-recursion as for structural recursion.
  - naasking 7mo ago
    True, but couldn't you just simulate it by enqueing a thunk/continuation?
  - twic 7mo ago
    Right, you could use co-recursion. Or you could just use a queue.
- mkbosmans 7mo ago
  No need for radical changes. def visit_bf(g): n, children = g yield n if children: iterators = [iter(visit_df(c)) for c in children] while iterators: try: yield next(iterators[0]) except StopIteration: iterators.pop(0) iterators = iterators[1:] + iterators[:1] The difference between DFS and BFS is literally just the last line that rotates the list of child trees. Python is a pretty mainstream language and even though the DFS case can be simplified by using `yield from` and BFS cannot, I consider that just to be syntactic sugar on top of this base implementation.
lacoolj 7mo ago
This page is a good example of when Typescript is both unnecessary and off-putting, based on the content's purpose. The author is trying to demonstrate a problem and the proposed solution, using example code that the reader then needs to read, formulate a visual "structure" in their mind, and then apply that structure to the subsequent code. Typescript is not in any way invalid here, and as a tool when programming something that will run in the real-world, can be invaluable. However, when writing anything you want someone to deeply comprehend, you want to use the least amount of text needed to get your point across. Adding types don't serve any purpose here. The types used are generics, which tell you nothing specific, hence the name, and the names given to the functions and object properties are enough to convey what this code is doing.
adafactor 7mo ago
PL-specific problem, but: the Rust borrow checker tends to give you a lot of trouble when writing iterative algorithms on nonlinear data structures, because it has trouble reasoning about partial borrows. The upcoming Polonius borrow checker is supposed to solve this, but it's still in alpha...
irenetusuq 7mo ago
[dead]
fifilura 7mo ago
Recursive solutions benefit from recursive solutions unless the solution is trivial.

48 points by luispa 7mo ago

This has always felt like the kind of thing we could be building compilers to solve. Recursive -> explicit stack is a very mechanical conversion, why can't we write a compiler transform pass that does that rewrite any time it detects a high potential for stack overflow?

Jaxan 7mo ago
Many compilers do change a recursion into a loop, avoiding the stack altogether!
Epa095 7mo ago
Yeah, tail call elimination, is definitely doable. Python famously does not have it because "Language inventor Guido van Rossum contended that stack traces are altered by tail-call elimination making debugging harder, and preferred that programmers use explicit iteration instead". https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call
derriz 7mo ago
It’s called TCO - tail call optimization - and gcc and llvm are supposed to implement it although tail recursive style code is probably uncommon in C or C++. Outside of that it’s common in functional languages where recursive functions are obviously idiomatic and so it has more potential to provide performance benefit. It’s not a purely local optimization - affecting the call structure so debugging is a pain point. Which is probably why most imperative language compilers don’t bother given the lack of utility for the vast majority of code bases. It feels like something that would need to be specified at the language spec or semantics level to make it useful rather than just making it optional for the compiler - otherwise the developer is probably just going to do the transform manually - to be safe - if stack explosion was a possibility if the compiler decided on a whim to not perform TCO.
- afiori 7mo ago
  Just like many languages have annotations for inlining functions they could have annotations for tco. From an usability pov i would like annotations for must, must not, should, and should not. Where the "must" versions error if the compiler can't do the optimization
  - a57721 7mo ago
    Scala and Kotlin have 'tailrec' annotation/modifier, though not as sophisticated as you describe.
- ufo 7mo ago
  Tail call optimization optimizes the situations where the recursion doesn't actually need any stack space, but I think the parent poster is asking about situations that aren't tail recirsive.
ufo 7mo ago
It's indeed very mechanical and some programming languages can do it for you. I think you're mainly asking for heap-allocated stacks. Some languages always use the heap for stack frames instead of the native stack and can set the stack limit as high as there's memory available. You might also want to look into stackful coroutines, which allow one to pause the execution of a recursive function and switch to another function. This can provide you with multiple call stacks, which is another reason people sometimes choose to use write explicit stacks.

jonathanlydall 7mo ago

It depends on whether the limited call stack capacity will be an issue for the particular problem you’re solving. I’m presently working on a problem which uses traversal of TypeScript file syntax trees. I can reasonably assume that we will never get a file with a deep enough syntax tree which would cause a stack overflow. A manually managed stack might seem safer, but as pointed out by this article the code would be more complicated and, in my case, for no good reason.

layer8 7mo ago
In practice, a heap-based manual stack can be as unsafe with unbounded input as using the native call stack (considering typical OOM behavior). If you have untrusted input, you might want to limit the stack depth in either case. And it’s not difficult to add a recursion counter to recursive calls. So I don’t think it’s an inherently distinguishing feature between the two approaches. Personally I tend to find the iterative approach easier to follow when no actual stack is needed, i.e. in the tail-call case.
randomNumber7 7mo ago
> I can reasonably assume that we will never get a file with a deep enough syntax tree which would cause a stack overflow. What if eve constructs a file specifically so that you get stack overflow?
- jonathanlydall 7mo ago
  Eve will then experience a stack overflow exception on our app running on her PC, no doubt she will be very impressed with her achievement.
  - randomNumber7 7mo ago
    Ok, but then your argumentation is only valid for programming languages with build in saftey guards. In low level languages this would be a recipe for disaster.
aleph_minus_one 7mo ago

twic 7mo ago

> It seems to be common knowledge that any recursive function can be transformed into an iterative function. Huh. Where i work, the main problem is that everyone is hell-bent on transforming every iterative function into a recursive function. If i had a pound for every recursive function called "loop" in the codebase, i could retire.

skeeter2020 7mo ago
My experience has gone the other way: lots of code with recursion, rewritten to be iterative. There really aren't that many use-cases in vanilla enterprise code that benefit from recursion when the entire cost is considered.
adafactor 7mo ago
Where on earth do you work? This is unusual...

twic 7mo ago

> This solution looks extremely similar to the previous one, which is a good thing. Our requirements have experienced a small change (reversing the traversal order) and our solution has responded with a small modification. Now do breadth-first traversal. With the iterative approach, you just replace the stack with a queue. With the recursive approach, you have to make radical changes. You can make either approach look natural and elegant if you pick the right example.

aleph_minus_one 7mo ago
> Now do breadth-first traversal. With the iterative approach, you just replace the stack with a queue. With the recursive approach, you have to make radical changes. The reason is that no programming language that is in widespread use has first-class support for co-recursion. In a (fictional) programming language that has this support, this is just a change from a recursive call to a co-recursive call.
- Chinjut 7mo ago
  Haskell (I realize this may not pass your threshold for widespread use) has equal support for co-recursion as for structural recursion.
- naasking 7mo ago
  True, but couldn't you just simulate it by enqueing a thunk/continuation?
- twic 7mo ago
  Right, you could use co-recursion. Or you could just use a queue.
mkbosmans 7mo ago
No need for radical changes. def visit_bf(g): n, children = g yield n if children: iterators = [iter(visit_df(c)) for c in children] while iterators: try: yield next(iterators[0]) except StopIteration: iterators.pop(0) iterators = iterators[1:] + iterators[:1] The difference between DFS and BFS is literally just the last line that rotates the list of child trees. Python is a pretty mainstream language and even though the DFS case can be simplified by using `yield from` and BFS cannot, I consider that just to be syntactic sugar on top of this base implementation.

lacoolj 7mo ago

This page is a good example of when Typescript is both unnecessary and off-putting, based on the content's purpose. The author is trying to demonstrate a problem and the proposed solution, using example code that the reader then needs to read, formulate a visual "structure" in their mind, and then apply that structure to the subsequent code. Typescript is not in any way invalid here, and as a tool when programming something that will run in the real-world, can be invaluable. However, when writing anything you want someone to deeply comprehend, you want to use the least amount of text needed to get your point across. Adding types don't serve any purpose here. The types used are generics, which tell you nothing specific, hence the name, and the names given to the functions and object properties are enough to convey what this code is doing.

adafactor 7mo ago

PL-specific problem, but: the Rust borrow checker tends to give you a lot of trouble when writing iterative algorithms on nonlinear data structures, because it has trouble reasoning about partial borrows. The upcoming Polonius borrow checker is supposed to solve this, but it's still in alpha...

irenetusuq 7mo ago

[dead]

fifilura 7mo ago

Recursive solutions benefit from recursive solutions unless the solution is trivial.