I must have missed this class. How does one convert a recursive descent parser into an iterative one?
In tail recursive algorithms, there is no stack, it's just a straight loop.
def foo(state, acc): # if acc is needed
if base-condition(state): return acc
return foo(next(state), f(state, acc))
def foo(state):
acc = initial
while not base-condition(state):
acc = f(state, acc)
state = next(state)
return acc
def search(node, val):
if node is None: return False # empty tree, only need this check once
stack = [node]
while stack:
n = stack.pop()
if n.val == val: return True
if n.right: stack.push(n.right)
if n.left: stack.push(n.left)
return False
When you have multiple mutually recursive functions (as is likely the case in a recursive descent parser) then things become more complicated, but it's still feasible.
That's basically what continuations provide. Scheme, SML, and others provide them.
Before I knew about CPS and defunctionalization, I wrote a Python decorator that did exactly the transformation you describe. https://github.com/tylerhou/fiber. Now I know about CPS and defunctionalization, I realize that my work was not the best implementation (but it was a fun learning experience!).
That only applies for non-primitive recursive functions, though. Most people rarely encounter those. For primitive recursive functions, it's all down to the nature of the function and what's idiomatic for your language. If you're using Scheme, for example, recursion is the name of the game.
Recursion isn't physically real, any book that teaches the abstraction before explaining either the call stack (for non-TCO recursion) or in the GOTO context is a book actively trying to gatekeeper CS and weed out readers. (Not that any of those old pascal turbo/boreland books from the 90s actually shipped code that compiled.)
I had several people on HN of all places try to "teach me" recursion after this simple line inside a larger comment:
> It's like acting like recursion is physically real (it's not) when it smuggles in the call stack.
Recursion IS real abstractly. It's just not physically real, it was developed before we knew how DNA/RNA encoding handles the same issues in a more performant way.
Recursive functions are a mathematical concept, like the "imaginary" number, or "trascendental" numbers. Or negative numbers for that matter.
Simple example, the Fibonacci sequence. FIB(1) = 1 FIB(2) = 1 FIB(N) = FIB(N-1) + FIB(N-2)
There's no programming language or "physical" implementation needed in order to calculate FIB(N) for arbitrary N. Pencil and paper will do for small numbers
But in computer programing it is often hidden.
And then you are misleading people about recursion and not helping them to build mental models that map to the physical/hardware process.
This isn't a big deal or anything, it's hardly worth talking about but it is literally a true thing many don't realize and that does empirically negatively effect education of the concept.
Recursive functions were mathematically defined well before the callstack or the von Neumann architecture was a thing. Godel, Church and Kleene did alot of work on them in the 1930s (and I believe even prior to that infinite series were defined recursively although functional theory had not be worked out), this was before ENIAC (1945) which would be just barely recognizable as a general purpose computer and didn't have anything like CALL instruction.
So I don't understand this notion of "hiding the callstack" comes from. If one cannot understand recursion without invoking the callstack, well thats just them. But I don't see how its absolutely necessary or some universal
I'm being quite clear that I take issue with how the concept has been taught in many programming books and courses.
You can see the ignorance and confusion in this very thread.
Do you also believe that loops and functions should only be taught after the call stack and goto are taught? Neither of them are real either by your measure.
What a silly sentiment.
They don't smuggle anything in conceptually, their abstraction doesn't leave anything critical to their structure out. They are real and can be physicalized as stand alone objects.
I see you've never tried to teach a software class to children or other learners, historically recursion is _very_ poorly taught by those who already understand the concept, but I'm not saying you have to care about that, a lot of people think there are too many programers already.
That was a sharp left turn -- how do you figure DNA/RNA are relevant here? I feel like iteration pre-dates our modern understanding of RNA in particular (though I could be mistaken) so I struggle to imagine how DNA/RNA were particularly informative in this regard.
Math majors cover hundreds of algorithms per semester often using recursion without thinking much of it. For that matter, same with "higher order functions" (e.g. derivative operators, or even just translation/scaling of a graph). Even in introductory calculus, students cover things like fixed points (e.g. I remember discussing d^4/(dx)^4 sin = sin almost immediately after introducing derivatives).
Thinking in terms of physical machines is useful for reasoning about performance, but seems like a distraction for learning to think logically/correctly, which seems like a more important first step?