1. Recursion
- Posted by don cole <doncole at ?acbell.net>
Jul 21, 2007
-
Last edited Jul 22, 2007
Hello Anyone,
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)
Is this correct?
I notice that recursion uses more code.
Don Cole
2. Re: Recursion
- Posted by Bryan So <sohim at ?aho?.com>
Jul 21, 2007
-
Last edited Jul 22, 2007
This is a shorter recursion
constant stuff={"oranges","apples","bananas"}
procedure hello(object stuff)
if length(stuff) > 0 then
puts(1,stuff[1]&"\n")
hello(stuff[2..$])
end if
end procedure
hello(stuff)
3. Re: Recursion
- Posted by Jason Gade <jaygade at yahoo?co?>
Jul 21, 2007
-
Last edited Jul 22, 2007
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.
4. Re: Recursion
don cole wrote:
>
>
> Hello Anyone,
>
> }}}
<eucode>
> constant stuff={"oranges","apples","bananas"}
>
> -- this is iteration
<SNIP>
>
> --this is recursion
>
>
> Is this correct?
>
> I notice that recursion uses more code.
>
> Don Cole
Hi Don,
Others will maybe give chapter and verse on this, but meanwhile here are
some points:
- I think I've read that any recursive process can be replaced by a
non-recursive one.
- Recursion does pile stuff up on the stack (is running separate operations).
- Some recursion can be criticized for merely being recursive for the sake
of recursion.
HOWEVER
- Sometimes it is the most elegant way to do something.
- Sometimes it is almost spooky in its effectiveness. Here is a paste from
RDS' queens.ex that solves a difficult puzzle: finding all the patterns that
8 queens can occupy without threatening each other on a chess board:
procedure place_queen(sequence queens)
-- place queens on a NxN chess board
-- (recursive procedure)
row r -- only need to consider one row for each queen
if length(queens) = N then
soln += 1
print_board(queens)
return
end if
r = length(queens)+1
for c = 1 to N do
if not conflict({r,c}, queens) then
place_queen(append(queens, {r,c}))
end if
end for
end procedure
The for-loop uses recursion to poke its nose into all the possibilities
and returns the answers, something some major mathematicians failed to do
in trying for years.
--Quark
5. Re: Recursion
Actually, I found my previous version of sum on this list, posted in 1999!
Very similar to what I just wrote:
http://www.openeuphoria.org/cgi-bin/esearch.exu?fromMonth=A&fromYear=4&toMonth=C&toYear=4&postedBy=Jason+Gade&keywords=enough+chatter+sum
Just goes to show that I've been stuck in the same coding loop for several years
now... I really need to learn gui programming one of these days.
--
"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.
6. Re: Recursion
don cole wrote:
> -- this is iteration
> --this is recursion
>
> Is this correct?
Yes, but not something that people might actually do.
This is iteration :
function facti(int n)
int res
res = 1
for i = 2 to n do
res *= i
end for
return res
end function
This is recursion :
function factr(int n)
if n <= 1 then
return 1
end if
return n * factr(n-1)
end function
--
Derek Parnell
Melbourne, Australia
Skype name: derek.j.parnell
7. Re: Recursion
Here's another article on recursion (that I haven't read yet). It's pretty long
and probably a bit advanced.
http://www-128.ibm.com/developerworks/linux/library/l-recurs.html
It covers C and Scheme (which, as a dialog of Lisp, I don't really grok) and
some assembly.
--
"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.
8. Re: Recursion
Derek Parnell wrote:
>
> don cole wrote:
>
>
> > -- this is iteration
> > --this is recursion
> >
> > Is this correct?
>
> Yes, but not something that people might actually do.
Why not?
>
> This is iteration :
>
> function facti(int n)
> int res
> res = 1
> for i = 2 to n do
> res *= i
> end for
> return res
> end function
>
> This is recursion :
>
> function factr(int n)
> if n <= 1 then
> return 1
> end if
> return n * factr(n-1)
> end function
>
>
> --
> Derek Parnell
> Melbourne, Australia
> Skype name: derek.j.parnell
Don Cole
9. Re: Recursion
DB James wrote:
>
> HOWEVER
>
> - Sometimes it is the most elegant way to do something.
>
> - Sometimes it is almost spooky in its effectiveness. Here is a paste from
> RDS' queens.ex that solves a difficult puzzle: finding all the patterns that
> 8 queens can occupy without threatening each other on a chess board...
(various snips)
> --Quark
When i was around 12 or 13 years old i found a way to solve the 8 queens
problem in my head. This might sound like a big deal to some people,
but actually it wasnt that hard because i found a quick way to do it
using another number base system. Anyone can do it using this method.
Of course i still think it's a good way to show how computer algos
work though, any way you decide to solve it.
Here's a hint...
The number base system is base 8, and each board column is thought of as
a power of 8.
> - Sometimes it is almost spooky in its effectiveness.
Spooky you say?
With the algorithm i was talking about in my previous post (the one
that had to calculate something to high accuracy) it was perhaps the
first time i saw something that actually resembled emergence on the
computer! The solution set seemed to 'emerge' from the input data,
and it's so darn accurate it is almost impossible to believe without
seeing; really almost spookie.
One little function that can call itself...so little code, such a
big problem solved!
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."
10. Re: Recursion
Al Getz wrote:
>
> DB James wrote:
> >
> > HOWEVER
> >
> > - Sometimes it is the most elegant way to do something.
> >
> > - Sometimes it is almost spooky in its effectiveness. Here is a paste from
> > RDS' queens.ex that solves a difficult puzzle: finding all the patterns that
> > 8 queens can occupy without threatening each other on a chess board...
>
> (various snips)
>
> > --Quark
>
>
> When i was around 12 or 13 years old i found a way to solve the 8 queens
> problem in my head. This might sound like a big deal to some people,
> but actually it wasnt that hard because i found a quick way to do it
> using another number base system. Anyone can do it using this method.
> Of course i still think it's a good way to show how computer algos
> work though, any way you decide to solve it.
>
> Here's a hint...
> The number base system is base 8, and each board column is thought of as
> a power of 8.
>
> > - Sometimes it is almost spooky in its effectiveness.
>
> Spooky you say?
> With the algorithm i was talking about in my previous post (the one
> that had to calculate something to high accuracy) it was perhaps the
> first time i saw something that actually resembled emergence on the
> computer! The solution set seemed to 'emerge' from the input data,
> and it's so darn accurate it is almost impossible to believe without
> seeing; really almost spookie.
> One little function that can call itself...so little code, such a
> big problem solved!
>
>
> Al
>
> E boa sorte com sua programacao Euphoria!
>
>
> My bumper sticker: "I brake for LED's"
>
Hello again,
I guess i should have also mentioned that for many chess players
the 8 queens problem isnt that hard for them to solve given 8
queens and a regular chess board. But this is not my main
reason for posting again...
> Spooky you say?
The algo i was talking about achieved quite a bit of extra functionality
from being able to call itself, and only a few tests were required
within the function to make the decisions to either call itself again
or call the long calculation routine again or exit. Just doing this
meant that the algo could follow the solution and break it into
smaller and smaller pieces if necessary, and the way this occurs makes
it seem as if it almost 'knows' what to do. It is able to 'adapt'
quite well to the input data, doing the same thing over and over
possibly going deeper and deeper into the problem until a solution is
found.
The beginnings of some sort of A.I. perhaps...
"I Recursion": Think about what you are thinking about when you
think about something--same thing. We solve problems by thinking
about something over and over until a solution emerges.
And adaptability...
I had begun to think about the Eu sequence as a bit of an evil, because
of the problems it can bring, not only to the programmer, but to the
operating system that has to deal with a complex data structure like
that when there is a lot of data. It's the data equivalent of the
'goto' statement, where it works just fine with a small (or medium)
data set, but as soon as the data becomes large problems pop up,
just as a large program with many goto's presents a program maintenance
problem.
But then there is the counter point,
in that the sequence is the ultimate adaptable data structure, so there
may be a place in the future for it after all.
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."
11. Re: Recursion
See recursion..
;)
Sorry could not resist
12. Re: Recursion
Al Getz wrote:
>
> Al Getz wrote:
> >
> > DB James wrote:
> > >
<SNIP>
> > > --Quark
> >
> >
> > When i was around 12 or 13 years old i found a way to solve the 8 queens
> > problem in my head. This might sound like a big deal to some people,
> > but actually it wasnt that hard because i found a quick way to do it
> > using another number base system. Anyone can do it using this method.
> > Of course i still think it's a good way to show how computer algos
> > work though, any way you decide to solve it.
> >
> > Here's a hint...
> > The number base system is base 8, and each board column is thought of as
> > a power of 8.
Al, are you trying to cause insomnia due to chess boards dancing in
programmer's heads with that "hint? 
> > > - Sometimes it is almost spooky in its effectiveness.
> >
> > Spooky you say?
> > With the algorithm i was talking about in my previous post (the one
> > that had to calculate something to high accuracy) it was perhaps the
> > first time i saw something that actually resembled emergence on the
> > computer! The solution set seemed to 'emerge' from the input data,
> > and it's so darn accurate it is almost impossible to believe without
> > seeing; really almost spookie.
> > One little function that can call itself...so little code, such a
> > big problem solved!
> >
That is just the kind of thing I meant -- where a small amount of code gives
big and often complex results. Some 8 queens solvers show the "backing out"
of unproductive paths and going on to other possibilities.
> > Al
>
> Hello again,
>
>
> I guess i should have also mentioned that for many chess players
> the 8 queens problem isnt that hard for them to solve given 8
> queens and a regular chess board. But this is not my main
> reason for posting again...
>
> > Spooky you say?
> The algo i was talking about achieved quite a bit of extra functionality
> from being able to call itself, and only a few tests were required
> within the function to make the decisions to either call itself again
> or call the long calculation routine again or exit. Just doing this
> meant that the algo could follow the solution and break it into
> smaller and smaller pieces if necessary, and the way this occurs makes
> it seem as if it almost 'knows' what to do. It is able to 'adapt'
> quite well to the input data, doing the same thing over and over
> possibly going deeper and deeper into the problem until a solution is
> found.
>
> The beginnings of some sort of A.I. perhaps...
> "I Recursion": Think about what you are thinking about when you
> think about something--same thing. We solve problems by thinking
> about something over and over until a solution emerges.
>
I have an old programming notion that has been helpful to me of the "blind
bloodhound" who can't see, but he always knows where he's been...
> And adaptability...
> I had begun to think about the Eu sequence as a bit of an evil, because
> of the problems it can bring, not only to the programmer, but to the
> operating system that has to deal with a complex data structure like
> that when there is a lot of data. It's the data equivalent of the
> 'goto' statement, where it works just fine with a small (or medium)
> data set, but as soon as the data becomes large problems pop up,
> just as a large program with many goto's presents a program maintenance
> problem.
Poo.
> But then there is the counter point,
> in that the sequence is the ultimate adaptable data structure, so there
> may be a place in the future for it after all.
>
>
> Al
>
This may be a place to stick something that I (and many others) read of
long ago and I'm not sure if I translated it from C or if I just got the
idea from one of Nelson Dewdney's writings... It is the binary search tree.
Some of the comment lately was on linked lists which reminded me of good old
recursion, so I cobbled together the following from memory. I haven't tested
it, so it could well have mistakes:
-- binary search tree in Euphoria
-- the data sequence will expand as it needs to
-- can be used to create a dictionary of words
constant WORD=1,NUM=2,LEFT=3,RIGHT=4
constant UNIT={"",0,0,0}
global sequence data
data={{"mean",0,0,0}} --to start, provide one "mid" word, but NUM is 0
procedure StoreTree(sequence word,integer loc)
integer cmpr,link
cmpr=compare(word,data[loc][WORD])
if cmpr=0 then --word exists, add to count
data[loc][NUM]+=1
elsif cmpr=-1 then --if word is less
if not data[loc][LEFT] then -- create new node
data=append(data,UNIT)
link=length(data)
data[loc][LEFT]=link
data[link][WORD]=word
data[link][NUM]+=1
else -- recursively follow the tree
Store(word,data[loc][LEFT])
end if
else -- if word is greater
if not data[loc][RIGHT] then -- create new node
data=append(data,UNIT)
link=length(data)
data[loc][RIGHT]=link
data[link][WORD]=word
data[link][NUM]+=1
else -- recursively follow the tree
Store(word,data[loc][RIGHT])
end if
end if
end procedure
--from a stream of words, call Store():
--word=NextFromStream()
--StoreTree(word,1)
Anyway, it is something like that, and it does use recursion to "follow its
nose" and the algorithm is quite happy to use sequences...
--Quark
13. Re: Recursion
- Posted by Al Getz <Xaxo at a?l.c?m>
Jul 25, 2007
-
Last edited Jul 26, 2007
DB James wrote:
>
> Al Getz wrote:
> >
> > Al Getz wrote:
> > >
> > > DB James wrote:
> > > >
> <SNIP>
> > > > --Quark
> > >
> > >
> > > When i was around 12 or 13 years old i found a way to solve the 8 queens
> > > problem in my head. This might sound like a big deal to some people,
> > > but actually it wasnt that hard because i found a quick way to do it
> > > using another number base system. Anyone can do it using this method.
> > > Of course i still think it's a good way to show how computer algos
> > > work though, any way you decide to solve it.
> > >
> > > Here's a hint...
> > > The number base system is base 8, and each board column is thought of as
> > > a power of 8.
>
> Al, are you trying to cause insomnia due to chess boards dancing in
> programmer's heads with that "hint?
>
> > > > - Sometimes it is almost spooky in its effectiveness.
> > >
> > > Spooky you say?
> > > With the algorithm i was talking about in my previous post (the one
> > > that had to calculate something to high accuracy) it was perhaps the
> > > first time i saw something that actually resembled emergence on the
> > > computer! The solution set seemed to 'emerge' from the input data,
> > > and it's so darn accurate it is almost impossible to believe without
> > > seeing; really almost spookie.
> > > One little function that can call itself...so little code, such a
> > > big problem solved!
> > >
> That is just the kind of thing I meant -- where a small amount of code gives
> big and often complex results. Some 8 queens solvers show the "backing out"
> of unproductive paths and going on to other possibilities.
>
> > > Al
> >
> > Hello again,
> >
> >
> > I guess i should have also mentioned that for many chess players
> > the 8 queens problem isnt that hard for them to solve given 8
> > queens and a regular chess board. But this is not my main
> > reason for posting again...
> >
> > > Spooky you say?
> > The algo i was talking about achieved quite a bit of extra functionality
> > from being able to call itself, and only a few tests were required
> > within the function to make the decisions to either call itself again
> > or call the long calculation routine again or exit. Just doing this
> > meant that the algo could follow the solution and break it into
> > smaller and smaller pieces if necessary, and the way this occurs makes
> > it seem as if it almost 'knows' what to do. It is able to 'adapt'
> > quite well to the input data, doing the same thing over and over
> > possibly going deeper and deeper into the problem until a solution is
> > found.
> >
> > The beginnings of some sort of A.I. perhaps...
> > "I Recursion": Think about what you are thinking about when you
> > think about something--same thing. We solve problems by thinking
> > about something over and over until a solution emerges.
> >
>
> I have an old programming notion that has been helpful to me of the "blind
> bloodhound" who can't see, but he always knows where he's been...
>
> > And adaptability...
> > I had begun to think about the Eu sequence as a bit of an evil, because
> > of the problems it can bring, not only to the programmer, but to the
> > operating system that has to deal with a complex data structure like
> > that when there is a lot of data. It's the data equivalent of the
> > 'goto' statement, where it works just fine with a small (or medium)
> > data set, but as soon as the data becomes large problems pop up,
> > just as a large program with many goto's presents a program maintenance
> > problem.
>
> Poo.
>
> > But then there is the counter point,
> > in that the sequence is the ultimate adaptable data structure, so there
> > may be a place in the future for it after all.
> >
> >
> > Al
> >
> This may be a place to stick something that I (and many others) read of
> long ago and I'm not sure if I translated it from C or if I just got the
> idea from one of Nelson Dewdney's writings... It is the binary search tree.
> Some of the comment lately was on linked lists which reminded me of good old
> recursion, so I cobbled together the following from memory. I haven't tested
> it, so it could well have mistakes:
>
> }}}
<eucode>
> -- binary search tree in Euphoria
> -- the data sequence will expand as it needs to
> -- can be used to create a dictionary of words
>
> constant WORD=1,NUM=2,LEFT=3,RIGHT=4
> constant UNIT={"",0,0,0}
>
> global sequence data
> data={{"mean",0,0,0}} --to start, provide one "mid" word, but NUM is 0
>
> procedure StoreTree(sequence word,integer loc)
> integer cmpr,link
> cmpr=compare(word,data[loc][WORD])
> if cmpr=0 then --word exists, add to count
> data[loc][NUM]+=1
> elsif cmpr=-1 then --if word is less
> if not data[loc][LEFT] then -- create new node
> data=append(data,UNIT)
> link=length(data)
> data[loc][LEFT]=link
> data[link][WORD]=word
> data[link][NUM]+=1
> else -- recursively follow the tree
> Store(word,data[loc][LEFT])
> end if
> else -- if word is greater
> if not data[loc][RIGHT] then -- create new node
> data=append(data,UNIT)
> link=length(data)
> data[loc][RIGHT]=link
> data[link][WORD]=word
> data[link][NUM]+=1
> else -- recursively follow the tree
> Store(word,data[loc][RIGHT])
> end if
> end if
> end procedure
>
> --from a stream of words, call Store():
> --word=NextFromStream()
> --StoreTree(word,1)
> </eucode>
{{{
>
> Anyway, it is something like that, and it does use recursion to "follow its
> nose" and the algorithm is quite happy to use sequences...
>
> --Quark
Hi DB,
Im not saying you shouldnt use them, just pointing out a few
things about them. I use them all the time
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."
