Possible Duplicate:
Can all iterative algorithms be expressed recursively?
Is it always possible to convert a iterative function in a recursive function?
views:
128answers:
5
A:
Depends on what the function do.
Of course you can, though, add this to your function:
void f(...) {
if(false) f(...)
else { processing }
}
In this case the second function is recursive, but recursion never happens.
Benoit
2010-09-26 18:07:17
A recursive function is a function that calls itself. If the call never happens, is it really recursive? I would say no.
IVlad
2010-09-26 18:09:46
Good point. But how do you design recursively a function that returns its argument plus one?
Benoit
2010-09-26 18:12:16
@Benoit - good question. Depending on the restrictions, it might be impossible. If you add another argument to the function however, or use a helper function, then it's possible. If you're assuming infinite precision arithmetic, then you can also do it with a single argument (because you have room to encode certain extra information in it).
IVlad
2010-09-26 18:18:56
A:
As far as I know yes, this is possible. The other way around is also possible, but in that case you may need to use appropriate data structures such as a stack.
Lucero
2010-09-26 18:08:00
The reverse is only possible if the function is *primitive* recursive. Not all recursive functions are, for example, the Ackermann function: [http://en.wikipedia.org/wiki/Ackermann_function] is impossible to express iteratively
TokenMacGuy
2010-09-26 18:10:03
If the function can be computed by a touring machine, you can convert any recursive function to an iterative one with a stack, which basically replicates what you would have on the call stack.
Lucero
2010-09-26 18:19:09
+2
A:
Algorithm and implementation of an algorithm are two different things. The term recursion also means different things, depending on whether it is applied to the algorithm itself or to its specific implementation. It is not clear from your question which one you are talking about.
It is always possible to convert recursive implementation into iterative implementation, where "recursive" and "iterative" are just syntactic properties of a program written in a procedural language, like C or C++.
It is generally impossible to turn recursive algorithm into an iterative algorithm, where "recursive" and "iterative" describe the fundamental structure of the algorithm itself.
AndreyT
2010-09-26 18:11:27
+1
A:
Yes
All iterative functions can be made recursive and vice versa. In functional languages it is common practice to rewrite iterative loops as tail-recursion. As long as the functional language is Turing-complete, and they all are, then it can compute any computable function. Therefore, any loop can be expressed iteratively.
DigitalRoss
2010-09-26 18:13:35
A:
The usual way an iterative function works looks something like this:
function iterative(args)
while not done_with(args)
args = transform(args)
end while
return args
end function
once you have transformed an iterative function into this form, it can then be trivially transformed into a recursive function like so:
function recursive(args)
if done_with(args)
return args
else
return transform(args)
end if
end function
TokenMacGuy
2010-09-26 18:14:36