Do all recursive fuctions also have a non-recursive version of itself?

Question

Is there any proof that states that any recursive function has to have a non-recursive function that has the same output as the recursive function?

Answer 1

"Recursive" is not a property of a function; it is a property of a particular implementation of a function. You can always avoid an explicit recursion by simulating the recursion "inline". One way to see this is to think about what a recursive function in a higher-level language looks like when compiled down to assembly code. There is no "recursion" in assembly code, because there are no explicit function calls at all, only memory reads and writes, primitive operations like addition and multiplication, and branching and jumping to particular locations.

Answer 2

If I understand you correctly, there are counterexamples. For example, I believe the Ackermann function is a recursively defined function which does not have a possible non-recursive definition.

The answer is incorrect; please remove the acceptance. I won't delete it:

1. to prevent someone else from making the same error
2. The comments are instructive.