4 ms·

Why is it called recursive descent, isn't that redundant? I normally think of any recursion as some kind of descent into deeper levels. Maybe I'm being biased

Why is it called recursive descent, isn't that redundant? I normally think of any recursion as some kind of descent into deeper levels. Maybe I'm being biased due to awareness of stackframes being a common way to implement recursion. Or maybe it's a known phrase made popular by a paper or researcher. like "embarrassingly parallel". There are other ways to say it but comp sci people know by convention what an embarrassing problem is and that it's usually a good thing. If everyone started saying only "recursive parser" would there really be any confusion?

megous 10y ago
> I normally think of any recursion as some kind of descent into deeper levels. Maybe I'm being biased due to awareness of stackframes being a common way to implement recursion. You can write bottom up algorithms using recursion too. It still technically goes down first, but does the real work on the way up.
- bjterry 10y ago
  For a simple example, this is like the difference between function sum(lst) { if (length(lst) > 0) { return head(lst) + sum(tail(lst)); } return 0; } vs. function sum(lst, currentSum) { if (length(lst) > 0) { return sum(tail(lst), currentSum + head(lst)); } return currentSum; } In the first case you don't actually start doing addition until after you get to the end of the list, while the latter is doing addition on the way down.
munificent 10y ago
> Or maybe it's a known phrase made popular by a paper or researcher. Right. "Recursive descent" is the canonical term for this style of parser. You conceivably could have a non-recursive descent parser if your language grammar didn't have any cycles. (For example, if you only supported arithmetic expressions and didn't have parentheses for grouping.) In practice, languages are almost always recursive. My hunch is that the inventor of recursive descent (can't remember his name at the moment) stressed "recursive" because recursive procedure calls were considered a fairly advanced topic at the time. Recall that this was back when Fortran didn't even support recursion. > If everyone started saying only "recursive parser" would there really be any confusion? Yes, "recursive ascent" is a thing too, though it was invented much later.

megous 10y ago

> I normally think of any recursion as some kind of descent into deeper levels. Maybe I'm being biased due to awareness of stackframes being a common way to implement recursion. You can write bottom up algorithms using recursion too. It still technically goes down first, but does the real work on the way up.

bjterry 10y ago
For a simple example, this is like the difference between function sum(lst) { if (length(lst) > 0) { return head(lst) + sum(tail(lst)); } return 0; } vs. function sum(lst, currentSum) { if (length(lst) > 0) { return sum(tail(lst), currentSum + head(lst)); } return currentSum; } In the first case you don't actually start doing addition until after you get to the end of the list, while the latter is doing addition on the way down.

munificent 10y ago

> Or maybe it's a known phrase made popular by a paper or researcher. Right. "Recursive descent" is the canonical term for this style of parser. You conceivably could have a non-recursive descent parser if your language grammar didn't have any cycles. (For example, if you only supported arithmetic expressions and didn't have parentheses for grouping.) In practice, languages are almost always recursive. My hunch is that the inventor of recursive descent (can't remember his name at the moment) stressed "recursive" because recursive procedure calls were considered a fairly advanced topic at the time. Recall that this was back when Fortran didn't even support recursion. > If everyone started saying only "recursive parser" would there really be any confusion? Yes, "recursive ascent" is a thing too, though it was invented much later.