3 ms·
> Recursion is rarely a good idea Umm, I really disagree. Recursion and tail-call semantics are enough to make it equivalent to iteration, except the state is
by duaneb 11y ago
> Recursion is rarely a good idea
Umm, I really disagree. Recursion and tail-call semantics are enough to make it equivalent to iteration, except the state is stored in the calls instead of explicitly outside the loop. What sucks is buggy code that does not handle cases. Depending on how you view functional languages, for instance, you could argue that iteration is necessarily implemented with recursion, and not vice-versa, and that explicit looping is only necessary to serialize it into steps (instructions).
Nonetheless, with both approaches you need to guard against multiple negative signs. Not much to do with recursion. His approach would have been fine if he had a signed? flag.
- userbinator 11y agoObserve that in this case, the difference between a non-tail call and a tail-call is a single '-'! If the compiler does tail-call optimisation, then the function can consume an unbounded amount of leading spaces, yet a large amount of leading '-' would overflow the stack. If it doesn't, then lots of leading spaces will also overflow. This is not what I'd consider obvious and intuitive behaviour if you were black-box testing this function. There is a reason why high-reliability coding standards forbid or severely restrict recursion. It's difficult to reason about the resource usage of recursive code, and it also leads to non-obvious failure modes like this.
- duaneb 11y agoWell, obviously the - is a base case and should be removed from successive recursions. And I don't think it is difficult to reason about resource usage. Tail-calls are very intuitive. Some languages (e.g. scala) allow you to force a call to be a tail call (or fail with an error). I suspect that preferring explicit over implicit is why coding standards forbid recursion. However, many algorithms become straight-up awkward when having to manipulate the "call stack" manually: see traversal of graphs. Finally, what you were really complaining about was the fact that he didn't handle multiple dashes. It has very little to do with recursion, which is just a different way to fold the same semantics you'd still have wrong with an iterative version. It would never overflow the stack because why would you accept unlimited minuses? You're not evaluating an expression, you're parsing a known format and can fail fast.