2 ms·

Loops aren’t recursion?

• antonvs 1y ago
  Loops and recursion are fundamentally equivalent. See e.g. https://textbooks.cs.ksu.edu/cc210/16-recursion/08-recursion-to-iteration/embed.html https://textbooks.cs.ksu.edu/cc210/16-recursion/08-recursion...
  • layer8 1y ago
    Only if you have indexable memory that you can use as a stack, which in the context of LMs isn’t a given. As another example, a finite-state-machine language can have loops, but it can’t recurse unless there is external memory it has access to in a way that it can serve as a stack. Regular expressions also fall into that pattern; they can loop, but they can’t recurse. For that you need a pushdown automaton: https://en.wikipedia.org/wiki/Pushdown_automaton https://en.wikipedia.org/wiki/Pushdown_automaton.