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?
Asked
Active
Viewed 331 times
2
-
2What exactly do you mean? – Andrés E. Caicedo Sep 09 '13 at 03:33
-
I don't understand why you accepted Avraham's answer... – Mariano Suárez-Álvarez Sep 09 '13 at 04:40
-
I'm sorry, my mistake. I am just wondering if for every function that is defined recursively, is there a non-recursive way to define it. If so, is it mathematically proven? I am asking because I want to know if I should look into solving a certain problem non-recursively. – TheKobra Sep 09 '13 at 05:57
-
@TheKobra, that is precisely what compilers do... – Mariano Suárez-Álvarez Sep 09 '13 at 15:35
2 Answers
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.
Ted
- 33,788
0
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:
- to prevent someone else from making the same error
- The comments are instructive.
Avraham
- 3,237
-
Why do you think there is no non-recursive implementation? – Mariano Suárez-Álvarez Sep 09 '13 at 03:46
-
1(It doesn't have a primitive-recursive implementation, but that is a rather different matter) – Mariano Suárez-Álvarez Sep 09 '13 at 03:47
-
-
1You can always replace a recursive defintion with a non-recurive definition by, for example, using a stack. – Mariano Suárez-Álvarez Sep 09 '13 at 04:52
-