Re: On recursion
DB James wrote:
>
>
> 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
Hi again DB,
Well i wish i could say i had that much fun 
What happens to me is that i find these papers on the web that
'supposedly' describe a way to do some things, and after coding
them out carefully and checking everything twice they still dont
work, so i end up always reinventing the wheel anyway!
I downloaded one paper just a few months ago, and the guy describes
this method as "very fast, very accurate, compared to other
methods", but when tested, the results, although fast, were comming
out to only maybe three digits whereas the older methods were doing
five or so. I ended up having to double check the theories from
scratch, to make sure the method was sound to begin with. As it
turned out, i got the same results he did, even after approaching
the problem from a different angle. Since these results were also
inaccurate, i could only conclude that he left something out.
I ended up have to invent a 'corrector' and finally, after hours
of work instead of maybe 45 minutes if the paper was written complete,
the accuracy came out to an unbelievable number of digits: sometimes
just as accurate as a full blown algebraic approach (15 digits on the
PC), and this was a purely numerical approach requiring no long,
drawn out algebraic expressions! The conclusion was that although
the algo he did give worked, it was imcomplete. Unfortunately this
cost me hours of work over several days.
Anyway, back to the point: recursion...
I have also found that since an Eu function can return a sequence
of multiple values, you can have your function return all the solutions
at one time. Your recursive calls can utilize either all of them
or just the last (more recent) one. This turns out to be quite handy
too.
More importantly however, and i think this should be part of the
'theory' of recursive functions (if it's not already), is that if the
recursive function has a lot of work to do and there is also the
possibility of an error occuring (such as numerical instability)
then the recursive function should be designed such that it has an
early exit mechanism. This allows the function to quickly return
even if it is knee deep in recursive calls and an error occurs.
If the function does not need to be reentrant (that is, reentrant
from the standpoint of the main program body) then here is a quick
example:
integer ErrorHasOccurred
ErrorHasOccurred=0
function Calculate(sequence x) --recursive
if ErrorHasOccurred then
return 0
end if
--main body of function that contains
--both recursive calls to Calculate() and
--calls to a function that takes a relatively long
--time to complete after making decision.
return
end function
In the above function, if the decision branch decides
to call Calculate() many many times recursively, it
takes just as many times to go through that
same set of lines of code (which eventually decides
to skip calling Calculate() again) just to
get to the last 'return' statement. But, if the
relatively long function finds an error and sets
'ErrorHasOccurred' to equal 1, for all those times
the only lines that have to be executed will be
if ErrorHasOccurred then return 0 end if
which allows the main function call to return
much sooner. This is especially true if the long
function has to check something again and leads to
another error which takes much more time.
Another way to do this is to make one element of the sequence
an error flag, and that way the main function call can be
entered from the main program body several times too if needed.
The main point being that the function has a quick way to return
once an error has occurred because it doesnt help to keep running
though the whole function just to get to that last 'return'.
> While improving the language and the libraries is a Good Thing, I will
> often happily reinvent the wheel for the sheer pleasure of it.
I find it a necessary evil with all the bad information on the Web.
Take care,
Al
E boa sorte com sua programacao Euphoria!
My bumper sticker: "I brake for LED's"
From "Black Knight":
"I can live with losing the good fight,
but i can not live without fighting it".
"Well on second thought, maybe not."
Take care,
Al
E boa sorte com sua programacao Euphoria!
My bumper sticker: "I brake for LED's"
From "Black Knight":
"I can live with losing the good fight,
but i can not live without fighting it".
"Well on second thought, maybe not."
|
Not Categorized, Please Help
|
|
