PROGRAMMING TODAY new approach in C strict runtime allows us to improve reccurency: call queue

PROGRAMMING TODAY new approach in C strict
runtime allows us to improve reccurency: call queue
Well acknowledged, astonished and reverded (random words
which meanning i dont know) professor fir from comp.lang.c
presented now aproach to strict recureency: call queue
In this article we will brifly show how it works and
slightli discuss some advantage of this new approach
Consider classic reccurency example, co called "flood fill"
recolorize_pixel_chain(int x, int y)
{
   if(map[y][x]==color_to_replace)
   {
    map[y][x]=replacement_color);
    recolorize_pixel_chain(x+1, y);
    recolorize_pixel_chain(x-1, y);
    recolorize_pixel_chain(x, y+1);
    recolorize_pixel_chain(x, y-1);
    }
}
this is kinda astonishingly simple solution hovever
there are few somewhat serios disadvantages of it making it less practically
usable..
I.
one problem is that the depth of recursion which such
code may achieve is quite high - and for example flod fill of
HD images which are 2 mega pixels big or more could need a stack
of range of few tens of megabytes (wchich for present pc having at least
4-8 GB ram are nothig shocking but still)
II.
the second problem is efficiency: passing a myriads of
ret values on call stack is most probably suboptimall
where iterative version of this code could avoid passing
retvalues only stuffing argumens in some array which maay
spare unnecessary bandwidth (details would need to be investigated
though)
III.
other problems may be found like ofr example the order in which
this algorithm choses pixels is somewhat 'unnatural'
IV.
yet other problem may be that this code could be hard to
be optimised for compiler, though theoretically it could be
optimised
the disadvantage of iterative method is hovever also present
its harder to write, less eradable and longer
Here comes the solution profesor fir proposed, it is called
"call queue" (by analogt to "call stack")
the idea is to mark some function calls to be placed on call
queueinstead of call stack, say for example you use keyword
queue tod enote that
recolorize_pixel_chain(int x, int y)
{
   if(map[y][x]==color_to_replace)
   {
    map[y][x]=replacement_color);
    queue recolorize_pixel_chain(x+1, y);
    queue recolorize_pixel_chain(x-1, y);
    queue recolorize_pixel_chain(x, y+1);
    queue recolorize_pixel_chain(x, y-1);
    }
}
the idea is then compiler met the queue keyword it
not generates call to function but stores the pointer to it and
the arguments into separate runtime 'list' (it is internal array)
and then continues execution of the parent function
here above the function will execute and during its execution it will
store 4 entries in call queue - the queue is then 'run' but
after the function ends
whebn the four functions from queue execute it will store another entries
in the queue - untill the queue will be emptied then the execution finishes
the disadvantages here are seen
I. it is almost the same simple as oryguinal simpel recursion
method
II. the depth of recursion will be more shallow as when new
entries are added old are removed and the call queue may be
set on circular ram area - it is for example queue may have 10 MB
but work on 100 MB working set (depending on case)
III. the efficiency problem are probably resolved and
probably this verion will not be slower than iterative method
- note in fact call adreses of function not need to be stored
in many cases as here above - as the same function is called
each time, only arguments need to be stored
IV. order in which the call queue choses pixels is more natural
profesor fir thinks it should be build in new c compilers
to enhance recursion abilities of c, hovver he not expect
the big compiler writers which are sometimes slow to
adapt new methods will do it soon but the solution is not
bad to quite professor
[read more articles of PROGRAMMING TODAY your new news programming
magazine]