OpenEuphoria

Re: On recursion

• Posted by DB James <larches at ?omcast.?et> Jul 21, 2007
• 549 views

Al Getz wrote:
> 
> DB James wrote:
> > 
<SNIP>
>
> In any case, I have found recursive use of functions to be quite handy
> in the past too.  For example, i had to call a function that performed
> a rather intensive algorithm, but inside it had to decide whether
> the results of that algo were accurate enough to return a value or
> if it should switch to a smaller step size (like 1/10 the original)
> and perform the same algo only on each of the new (smaller) 10 steps
> (the algo gets more and more accurate as the step size is reduced,
> but small step size is not required to get accurate results over all
> the time frame).
>
> This doesnt sound too hard to do, but what makes it interesting is
> that once *those* 10 steps are started, it may become necessary to
> break one of those steps into 10 parts too, and then that could
> happen also with those 10 parts too, etc.  It requires much less
> code to write this kind of thing as a recursive function so that
> the function can perform the accuracy test and then call itself 10 
> times if need be, and within those 10 new smaller parts perform the
> same test and possibly call itself again 10 more times for each of
> those larger 10 parts (or just some of them).
> It worked out pretty nicely.
> 
> 
> Al

Hi Al,

Good reply, Al, Thanks.  I noted your "but what makes it interesting is..."
and wanted to answer to that.  While sometimes programming is like typing,
other times it is a pure pleasure, a series of discoveries that, even though
others may have got there long ago, it is new again when we personally find
it.  I have often avoided reading how others solved a problem for the fun of
finding a solution.

Your example of the recursion to fine-tune an answer is a good one.  The
user doesn't have to tell the algorithm how to proceed, it adjusts its
behavior as needed to get the job done.  Cool.

Here is an example of a small discovery of mine (and yes I know it probably
be done better) recently:
--=====================================================================
global function Chance(atom chance)
    --input is a number>0 and <1
    --output is 1 if the chance occurred, 0 otherwise
    --e.g.: Chance(3/100) ==> .03 ==> 3000 chances in 100000 total chances
    integer iPower
    atom totChances
    if chance<=0 or chance>=1 then return 0 end if
    iPower=0 --power(10,0)=1
while chance<1000 do chance*=10 iPower+=1 totChances=power(10,iPower) end
    while
    if rand(totChances)<=floor(chance) then return 1 end if
    return 0
end function
--=====================================================================

It is used this way:
if Chance(77/100) then doWhatever() end if

The line that was enjoyable to figure out was (and re-formatting):
while chance<1000 do
    chance*=10
    iPower+=1
    totChances=power(10,iPower)
end while

It isn't recursion, but does "call itself" to "zoom-up" the numbers until
they are a certain size so rand() can do its thing.

While improving the language and the libraries is a Good Thing, I will
often happily reinvent the wheel for the sheer pleasure of it.

--Quark