Comment by Jtsummers

Every recursive algorithm can be made into an iterative algorithm if you use an explicit stack instead of the implicit call stack. It's not always cleaner.

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

Is simply:

  def foo(state):
    acc = initial
    while not base-condition(state):
      acc = f(state, acc)
      state = next(state)
    return acc

If it's not tail recursive you introduce a stack, for instance a DFS on a binary tree:

  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

Note the insertion order is reversed from the recursive calls in a typical DFS. We want left to be searched first and then its children and then we "recur" back to right and deal with its children, so we need to push right into the stack first and then left.

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.