OpenEuphoria

Re: On recursion

• Posted by CChris <christian.cuvier at agric?lture.go?v.fr> Jul 21, 2007
• 548 views

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