OpenEuphoria

Re: Recursion

• Posted by Jason Gade <jaygade at yahoo?co?> Jul 21, 2007
• 708 views

don cole wrote:
> 
> 
> Hello Anyone,
> 
> }}}
<eucode>
>  constant stuff={"oranges","apples","bananas"}
>  
>  -- this is iteration
>  
>  procedure hello(object stuff)
>    for x=1 to length(stuff)  do
>         puts(1,stuff[x]&"\n")
>    end for
>  end procedure
>  
>  hello(stuff)
>  
>  --this is recursion
>  
>  procedure hello2(integer x)
>     if  x>length(stuff) then
>     else
>       puts(1, stuff[x]   &"\n")
>        hello2(x+1)
>     end if
>  end procedure
> 
> hello2(1)
> 
> </eucode>
{{{

> 
> Is this correct?
> 
> I notice that recursion uses more code.
> 
> Don Cole

But what if stuff was a sequence of indeterminate depth? For Euphoria, that's
where recursion would come most in handy.

Again, not every algorithm is better with recursion than with iteration. But
some are.

I first learned about recursion a long time ago with LOGO. It took me awhile to
really understand it. See the wiki page again for the factorial example -- they
give both an iterative as well as a recursive example.

We've been talking about min and max a lot lately -- imagine if you wanted to
extract the minimum or maximum value from a sequence of indeterminate depth? Or
if you wanted to sum a sequence like that?

I know I wrote a recursive sum routine before, but I never submitted it and I
don't know if I have a copy. Let's see if I can come up with one on the fly:

-- untested
function sum(sequence list)
    object element
    atom total
    
    total = 0
    element = {}

    for i = 1 to length(list) do
            element = list[i]
            if atom(element) then
                total += element
            else
                total += sum(element) -- sum the subsequence
            end if
    end for
    
    return total

end function

I really can't think of a way to solve this problem iteratively, even though it
may not be a common problem. I'll test it and get back with you if it doesn't
work.

--
"Any programming problem can be solved by adding a level of indirection."
--anonymous
"Any performance problem can be solved by removing a level of indirection."
--M. Haertel
"Premature optimization is the root of all evil in programming."
--C.A.R. Hoare
j.