[Developers] OD example on the danger of recursive programming

[Fidel Reyes Ramos]

Dear people,

>From my point of view, I see the source of the problem described in the
attached message is using global variables. 

Have you tried in this form?


PosID RowColIterator::next(<type> curpid_, <type> PosID)
{
    if ( !nextGridPoint( curpid_ ) )
        return mUdf(PosID);

    if ( !curpid_.isDefined() )
        return next(curpid_, PosID);

    return curpid_;
}

Each recursion call has it own variable, so an accuarate reference is made
in each recursive call.

My modest advice is: When using recursion, do not use global variables, make
them arguments of the function calling itself.

I hope this works better.
Regards.

-----Mensaje original-----
De: developers-bounces at opendtect.org
[mailto:developers-bounces at opendtect.org] En nombre de Jaap Glas
Enviado el: Miércoles, 03 de Octubre de 2007 09:02 a.m.
Para: developers at opendtect.org
Asunto: [Developers] OD example on the danger of recursive programming

Dear fellow developers,


An OpendTect example on the danger of recursive programming.
============================================================

Recursion is a very powerful mechanism available in many modern programming
languages. A lot of problems can be solved by more elegant algorithms when
using recursion, for example the faculty function. Some other problems can
hardly be solved without using recursion. The famous Towers of Hanoi is one
of them. However, recursive programming turns out to be not always without
danger. This is illustrated by the following example from our OpendTect code
that came across some time ago.

The task of the class RowColIterator is to iterate over all grid positions
where the surface (for instance a horizon) is defined. After initialization,
a function next() can be called to ask for the next surface position. The
(meta) code below shows the original implementation. The next() function is
called recursively if the surface is undefined at the next grid position.
An elegant solution that did survive the initial test stage:

PosID RowColIterator::next()
{
    if ( !nextGridPoint( curpid_ ) )
        return mUdf(PosID);

    if ( !curpid_.isDefined() )
        return next();

    return curpid_;
}

Some mysterious crashes were reported later on. These showed up after users
had continued their horizon picking on a new crossline that was a few lines
apart from the already existing horizon part. Not for every survey, not on
every platform, but still. What was going on?

Somewhere the RowColIterator had to traverse along several empty lines of
grid positions before finding a position at which the surface was defined
again. Meanwhile a new stackframe was pushed onto the stack for every next
grid position at which the surface was undefined. Depending on the length of
a crossline and the size of the stack, this finally had to result in a stack
overflow! No other option than replacing our recursive solution by some
iterative counterpart:

PosID RowColIterator::next()
{
    do
    {
        if ( !nextGridPoint( curpid_ ) )
            return mUdf(PosID);
    }
    while ( !curpid_.isPosDefined() );

    return curpid_;
}

A smart compiler could have detected this so-called tail recursion, and
could have rewritten it automatically into an iterative form. Apparently,
the gcc-compiler does not, or at least not with our current settings.
It is common practice in compilers for functional languages however.

Having a background in functional programming, I really like the elegance of
recursion, but it simply turned out to be not such a good idea in this
particular case. I think it is good to remember this example in case you are
applying recursion yourself a next time.


Best regards,

Jaap Glas

--
-- dr. Jaap C. Glas
-- Software Engineer
-- dGB Earth Sciences
-- Nijverheidstraat 11-2
-- 7511 JM Enschede, The Netherlands
-- jaap.glas at dgb-group.com
-- http://www.dgb-group.com
-- Tel: +31 534315155, Fax: +31 534315104

_______________________________________________
Developers mailing list
Developers at opendtect.org
http://lists.opendtect.org/mailman/listinfo/developers