Is recursion to iteration or vice versa algorithm exists?

Question

Is recursion to iteration or vice versa algorithm exists with most efficiency output and tail recursion?

Preferable panguage is C#.

For example: on input this algorithm get next simple function:

public static ulong Factorial(ulong n)
{
    return n == 0 ? 1 : n * Factorial(n - 1);
}

And after processing return following:

public static ulong Factorial(ulong n)
{
    ulong result = 1;
    for (ulong i = 1; i <= n; i++)
        result = result * i;
    return result;
}

Are you asking for a code converter, that takes as input a recursive algorithm in a particular language and returns an iterative algorithm in that language? — Michael Petrotta, Sep 16 '12 at 19:05
@KvanTT: this is *strictly* related to the language domain you're going to use. And by the way, there is no any relation with *algorithm*. This is, if I right understood the question, is *transformation* of the code, maintaining it's semantic. Don't think that exist a tool like this yet in CS. — Tigran, Sep 16 '12 at 19:08
@Michael Petrotta, yes. There are many descriptions how to convert it manually, but no explanations how to do it algorithmically. For this purpose parsers must be used at the beginning. — Ivan Kochurkin, Sep 16 '12 at 19:10
There is a trivial rewrite from recursion to iteration, using an explicit stack. But you can't easily rewrite one algorithm to a completely different one, as in your example above. It may work for some special cases, but probably not for the general case. — CodesInChaos, Sep 16 '12 at 19:11
For an algorithm to convert the code manually, have a look at [how to rewrite a recursive method by using a stack?](http://stackoverflow.com/a/7293515/76217) — dtb, Sep 16 '12 at 19:13
@CodesInChaos: don think it's yet possible to achieve with reasonable amount of automation. As much as I know yet noone succeeded in this. — Tigran, Sep 16 '12 at 19:27
possible duplication of: http://stackoverflow.com/questions/1549943/design-patterns-for-converting-recursive-algorithms-to-iterative-ones — Victor, Sep 17 '12 at 06:08

score 2 · Answer 1 · answered Sep 16 '12 at 19:11

Yes, it is always possible to create an iterative version from a recursive algorithm. I don't know if a program/code rewriter exists for C# to do that. This kind of technique has been well studied and you can find general references like From recursion to iteration: what are the optimizations? (pdf file).
The worst case would to simply "emulate" the stack on the heap to save the state of the function for future use. The simpliest case would probably be tail recursion to loop. There's plenty of articles on that subject.
On the other hand, creating a recursive version from a general iterative algorithm is less studied, but it certainly exists,

score 0 · Answer 2 · answered Sep 16 '12 at 19:12

0

the only thing i know is, recursion can be equally converted to non-recursion with stack, cause it's actually done that way, you can just do it by yourself.

btw, you may think of some cases not able to be converted to simple iteration.

answered Sep 16 '12 at 19:12

iloahz

4,491
8
23
31

Yes, every recursion can be converted to iteration with stack and it's pretty simple. But in many cases conversion to non-stack versions is possible (for example in factorial and fibonacci numbers) and it's more interesting and complex. – Ivan Kochurkin Sep 16 '12 at 19:24

Ohad · Answer 3 · 2012-09-16T19:30:18.697

I do not know of a trivial, generic, implementation of an algorithm which does this kind of transformation, but it is trivial to optimize recursive algorithms using dynamic programming methods, which are quite generic.

If, say, you cache the result of each Factorial call in a dictionary (a map from n -> Factorial(n)), you will get an algorithmic complexity which is equal to the iterative one (but! only time complexity. More memory is used in this method). Note that simply 'imitating' your own stack gives you nothing in terms of algorithmic complexity.

Caching is extremely easy to both implement and apply, and works for a wide range of algorithms.

The Wikipedia page has a specific entry on your example algorithm.

Is recursion to iteration or vice versa algorithm exists?

3 Answers3