In article <3eb4673c@news.povray.org>, Warp <war### [at] tagpovrayorg> 
wrote:

> Christopher James Huff <cja### [at] earthlinknet> wrote:
> > Can you give an example of one of these?
> 
>   I don't remember any. (Can quicksort be made iteratively?)

Can you remember any special terms I could use to look for information 
on these?


> > How about a slight modification: You can make an iterative version of 
> > any recursive algorithm that can be executed by a computer.
> 
>   There are algorithms which need a stack (which size is proportional
> to the amount of loops done). These are recursive algorithms which can't
> be done iteratively.

They can be done iteratively, you just need a stack. The problem may be 
the definitions we're using: by "iterative" I mean an implementation 
using a loop instead of recursive functions. I'm talking about the 
implementation in a language that supports loop structures (not POV 
functions) and/or recursion (also not POV functions). You can use 
recursion, or you can use loops and stacks. A VM or CPU are iterative, 
though you could mathematically define them as recursive. I don't know 
if this is any kind of standard definition, so don't take this as expert 
counsel.

BTW, something semi-related: I've got a working VM for Amber and am 
working on the compiler, and recently made some improvements to 
Sapphire, which should see another preview release soon. (After this 
semester ends...I haven't had much time to work on either.)
Among the improvements: objects now use copy-on-write. Actually, a kind 
of dual copy-on-write: methods and data are copied separately, and at 
another level the members are copied when used individually. 
Unfortunately, this means 3 integers overhead for reference counts, so 
objects aren't very memory efficient if you have lots of unique objects. 
That's what Amber is for, though, Sapphire just isn't designed for 
efficiency (though it is still much faster than a directly interpreted 
language like POV script).

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message