Translating recursive functions into iterative functions

[Paul]

Can anyone give me any guidelines, perhaps by giving a reference, on the general technique on translating recursive algorithms into iterative algorithms?

For example, the basic (inorder/ preorder/ postorder) traversals of binary trees are trivial to implement recursively. I've heard it said that these methods can be done iteratively using a stack, but I can't find it implemented anywhere.

Thank You,

Paul

[Scott Lurndal]

Paul <peps...@gmail.com> writes:
>Can anyone give me any guidelines, perhaps by giving a reference, on the general technique on translating recursive algorithms into iterative algorithms?
>
>For example, the basic (inorder/ preorder/ postorder) traversals of binary trees are trivial to implement recursively. I've heard it said that these methods can be done iteratively using a stack, but I can't find it implemented anywhere.
>

Recursion _is_ iteration using a stack.

Mimic it.

[Chris Vine]

In the functional languages, iteration on the one hand traditionally
refers to recursion in tail position (where tail call elimination is
possible so it has effect as what would be a loop construct in
imperative languages), and recursion on the other hand refers to
recursion not in tail position. The first generally involves passing
intermediate accumulated results as an argument to the recursively
called function, and the second involves storing intermediate results
as return values on the call stack.

What the difference is in C++ is anyone's guess, because recursing in
tail position is difficult because of destructors/RTTI. In an
imperative language, do what suits them. That does not often involve
extensive recursion.

This is an introductory text from the functional standpoint:
https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 .
That may or may not be what you had in mind.

Chris

[Chris Vine]

On Tue, 17 Nov 2015 19:44:57 +0000
Chris Vine <chris@cvine--nospam--.freeserve.co.uk> wrote:

> On Tue, 17 Nov 2015 08:42:05 -0800 (PST)
> Paul <peps...@gmail.com> wrote:
> > Can anyone give me any guidelines, perhaps by giving a reference, on
> > the general technique on translating recursive algorithms into
> > iterative algorithms?
> >
> > For example, the basic (inorder/ preorder/ postorder) traversals of
> > binary trees are trivial to implement recursively. I've heard it
> > said that these methods can be done iteratively using a stack, but I
> > can't find it implemented anywhere.
>
> In the functional languages, iteration on the one hand traditionally
> refers to recursion in tail position (where tail call elimination is
> possible so it has effect as what would be a loop construct in
> imperative languages), and recursion on the other hand refers to
> recursion not in tail position. The first generally involves passing
> intermediate accumulated results as an argument to the recursively
> called function, and the second involves storing intermediate results
> as return values on the call stack.
>
> What the difference is in C++ is anyone's guess, because recursing in
> tail position is difficult because of destructors/RTTI.

^^^^^^^^^^RAII

[Alf P. Steinbach]

A recursive call corresponds to pushing a state on a stack. For the
mechanical translation of recursive calls to iterative code, as the
compiler does with C++ code, the state pushed includes a return address,
i.e. where to continue when that state is popped. For a simulation of
that in C++ I think it would be easiest to use case label values as
simulated return addresses, and to think of the rest of the state as the
current local variables' state, instead of as call arguments.

For more intelligent human level translation of recursive to iterative,
algorithm transformation, one may think instead of what sequence of
states the stack will hold at any time.

* * *

As a first example consider Euclid's greatest common divisor algorithm:

auto gcd1( int const a, int const b )
-> int
{ return (b == 0? a : gcd1( b, a%b )); }

The idea is simply that if a>b, then either b is the greatest common
divisor D, or else, since there's a whole number of D's in b, and then
further a whole number of D's in a-b, D must be the common divisor of
a-b and b. And to avoid the inefficiency of Euclid's repeated
subtraction, we just reduce that immediately to a%b and b.

The recursive call pushes a pair of numbers on a stack, so you can
translate it like this:

using Pair = pair<int, int>;

auto gcd2( int const a, int const b )
-> int
{
stack<Pair> s;
s.push( Pair{ a, b } );
for( ;; )
{
Pair const current = s.top();
s.pop();
if( current.second == 0 ) { return current.first; }
s.push( Pair{ current.second, current.first%current.second } );
}
}

In this code the stack will never have more than one item, so it can be
replaced with a single variable:

auto gcd3( int const a, int const b )
-> int
{
Pair current = {a, b};
for( ;; )
{
if( current.second == 0 ) { return current.first; }
current = Pair( current.second, current.first%current.second );
}
}

And then there are a number of further trivial simplifications, which I
leave to you.

* * *

With the basics covered, let's do an inorder traversal of a binary tree:

void display1( Node const* const root )
{
if( root == nullptr ) { return; }
display1( root->left );
cout << root->value << ' ';
display1( root->right );
}

Each recursive call pushes a pointer onto a stack. Expressing both
recursive calls as iteration is difficult to do immediately. But the
first recursive call is not so difficult:

void display2( Node const* const root )
{
stack<Node const*> s;
Node const* p = root;
while( p != nullptr )
{
s.push( p );
p = p->left;
}
while( not s.empty() )
{
Node const* const current = s.top();
s.pop();
cout << current->value << ' ';
display2( current->right );
}
}

The idea here is to display the left subtree plus the root node, with
the help of the single remaining recursive call, and then to let that
call also handle the right subtree.

Now for the remaining recursive call, it clearly pushes the right child
node pointer onto the stack, and then proceeds left again:

void display3( Node const* const root )
{
stack<Node const*> s;
Node const* p = root;
while( p != nullptr )
{
s.push( p );
p = p->left;
}
while( not s.empty() )
{
Node const* const current = s.top();
s.pop();
cout << current->value << ' ';
Node const* p = current->right;
while( p != nullptr )
{
s.push( p );
p = p->left;
}
}
}

But at least for me it's not entirely obvious at a glance that this
should work, so I tested it with a little 7-node tree. Disclaimer: there
may be bugs still. But it worked with that tree.

Now, this code has the form of an unrolled LOOP-AND-A-HALF, so, roll
that loop back up:

void display4( Node const* const root )
{
stack<Node const*> s;
Node const* p = root;
for( ;; )
{
while( p != nullptr )
{
s.push( p );
p = p->left;
}
if( s.empty() )
{
return;
}
Node const* const current = s.top();
s.pop();
cout << current->value << ' ';
p = current->right;
}
}

Some further simplifications may be possible but, again, I leave that to
you.

* * *

Typically a problem either fits a recursive or an iterative form. GCD is
an exception, it's just about equally well expressed as recursive or
iterative (I suspect this holds in general for any tail-recursive
function, that it's just about equally as clear when expressed
iteratively). But the in-order traversal above is much more clear to me
as recursive function than as iterative. And this should IMO be the main
consideration. Not whether one can possibly shave off a nanosecond or
two, but which approach yields the most clear and easiest to understand
code.


Cheers & hth.,

- Alf

[Alf P. Steinbach]

On 11/18/2015 12:22 AM, Alf P. Steinbach wrote:
> [code]

Sorry for writing both Pair{a,b} and Pair(a,b). I started with a simple
struct, requiring {}, then changed that to a typedef of std::pair.
Imperfect, yes.

Cheers,

- Alf

[Juha Nieminen]

Paul <peps...@gmail.com> wrote:
> Can anyone give me any guidelines, perhaps by giving a reference, on the general technique on translating recursive algorithms into iterative algorithms?
>
> For example, the basic (inorder/ preorder/ postorder) traversals of binary trees are trivial to implement recursively. I've heard it said that these methods can be done iteratively using a stack, but I can't find it implemented anywhere.

Technically speaking "iterative" means that you don't need a stack (which
size is proportional to the number of iterations). Even if you avoid
calling the same function from within itself, ie. you seemingly avoid
recursion, if you nevertheless need a stack of data which size is
proportional to the number of iterations, your algorithm is recursive.

Some algorithms can be implemented recursively and genuinely
iteratively (such as merge sort), but others can't (such as quicksort).

Oftentimes forcefully trying to make a naturally recursive algorithm
into an iterative one (either a genuine or a faux one) only makes
the program more complex than it needs to be. (However, depending on
the case it might make it more efficient, but not always.)

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---