Is it always possible to write a non-recursive form for every Recursive function?

Technology CommunityCategory: RecursionIs it always possible to write a non-recursive form for every Recursive function?
VietMX Staff asked 3 years ago

When you use a function recursively, the compiler takes care of stack management for you, which is what makes recursion possible. Anything you can do recursively, you can do by managing a stack yourself (for indirect recursion, you just have to make sure your different functions share that stack).

A simple formal proof is to show that both µ recursion (general recursive function) and a non-recursive calculus such as GOTO are both Turing complete. Since all Turing complete calculi are strictly equivalent in their expressive power, all recursive functions can be implemented by the non-recursive Turing-complete calculus.