Are some algorithms inherently recursive? As in, rewriting it in tail-recursive/iterative form with a stack is still needed, and there is no way to do it otherwise.

I am asking because I struggled to implement the function stringsMatchingPrefix on a Trie tail-recursively without a stack. The stringsMatchingPrefix problem is: given a string P, find all the words in the trie with the prefix P.

  • 2
    $\begingroup$ Can you explain what stringsMatchingPrefix is? We cannot read your mind. $\endgroup$ Sep 20, 2020 at 9:33
  • $\begingroup$ Welcome! What do you mean "like" in your title and question? $\endgroup$ Sep 23, 2020 at 12:09
  • 1
    $\begingroup$ It's difficult to argue that a given algorithm needs some particular technique, since that requires us to precisely define that technique so as to rule out any trivial modifications to it (and for that matter, we also have to define what we mean by "[that particular] algorithm" - specifically, we need some notion of when two algorithms are the same, and that's surprisingly intricate). $\endgroup$ Sep 23, 2020 at 19:50
  • 1
    $\begingroup$ However, we can get somewhat satisfying results by showing that a given function we're trying to compute is not in a particular complexity class: e.g. the fact that the Ackermann function is not primitive recursive does in some sense say that there is no algorithm computing it which doesn't use "high-level" recursion (or something morally equivalent to that). $\endgroup$ Sep 23, 2020 at 19:50


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.