[Developers] OD example on the danger of recursive programming

[Jaap Glas]

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