1. On recursion
Hi,
To be sure, recursion is sometimes the way to go. I recently found myself
using the pattern below several times in writing string functions (probably
discovered a hundred times by Euphorians):
--======================================================================
global function StringFunc(sequence s)
--basic pattern of several functions
--handles 1 or many strings in s
if not length(s) then
return s
elsif atom(s[1]) then
--process single string
else
for i=1 to length(s) do
s[i]=StringFunc(s[i])
end for
end if
return s
end function
--======================================================================
Some recursive functions are obscure, but this pattern is clear and
obviously useful when processing one string or many.
--Quark
2. Re: On recursion
DB James wrote:
>
> Hi,
>
> To be sure, recursion is sometimes the way to go. I recently found myself
> using the pattern below several times in writing string functions (probably
> discovered a hundred times by Euphorians):
>
> }}}
<eucode>
> --======================================================================
> global function StringFunc(sequence s)
> --basic pattern of several functions
> --handles 1 or many strings in s
> if not length(s) then
> return s
> elsif atom(s[1]) then
> --process single string
> else
> for i=1 to length(s) do
a > s[i]=StringFunc(s[i])
> end for
> end if
> return s
> end function
> --======================================================================
> </eucode>
{{{
>
> Some recursive functions are obscure, but this pattern is clear and
> obviously useful when processing one string or many.
>
> --Quark
Recursion is a powerful, succesful problem analysis technique. However, a
recursive implementation is not always the most efficient one, because many
routine calls imply intensive use of the stack, and this is not the fastest thing
CPUs do nowadays, even when they do have a stack (Intel processors always have
had a stack, but this is not true for other makers).
A further note: recursion divides a problem into independent, smaller parts,
counting on the smaller parts to eventually have a direct soution and aggregating
them. In real life situations, the parts often bear some relationships between
one another that help solve the global problem, and which recursion ignores
because of its very anature. And the cost of the aggregation part is sometimes
hidden, but high. Recursion still works, but is kind of a brute force approach
which is not always the fastest.
In Euphoria, recursion which is not reflexive - routine_a() calls routine_b()
who calls routine_c() who calls routine_a() ... - requires the use o one or more
indirect calls using call_func() or call_proc(), because that's the only way to
call a routine before it is declared, which must necessarily happen once or more
in the cycle. This is inconvenient as many people already remarked; I never
checked whether this added any noticeable overhead. At least a temp for the
indirect call arguments. And, in reflexive recursion, you have to repeatedly save
all temps and privates of the routine, and restoring them; this has a cost too.
CChris
3. Re: On recursion
DB James wrote:
>
> Hi,
>
> To be sure, recursion is sometimes the way to go. I recently found myself
> using the pattern below several times in writing string functions (probably
> discovered a hundred times by Euphorians):
>
> }}}
<eucode>
> --======================================================================
> global function StringFunc(sequence s)
> --basic pattern of several functions
> --handles 1 or many strings in s
> if not length(s) then
> return s
> elsif atom(s[1]) then
> --process single string
> else
> for i=1 to length(s) do
> s[i]=StringFunc(s[i])
> end for
> end if
> return s
> end function
> --======================================================================
> </eucode>
{{{
>
> Some recursive functions are obscure, but this pattern is clear and
> obviously useful when processing one string or many.
>
> --Quark
Hi DB and CChris,
Recursion can be very useful when the underlying system can take
the stack build up, and im pretty sure Euphoria can. Im not sure
how this affects speed however, once the RAM gets filled (any system).
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.
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."
4. Re: On recursion
- Posted by DB James <larches at ?omcast.?et>
Jul 21, 2007
-
Last edited Jul 22, 2007
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
5. 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."
