In article <3eb3dcbc@news.povray.org>, gimi <gim### [at] psicoch> wrote:

> AFAIK this is only proven to be true for end-recursive algorithms
> (though /many/ of the functions with a single recursion call can
> be made end-recursive; but you will usually run into trouble if
> the algorithm has multiple recursive calls).

By multiple recursions, you mean multiple recursions from a single 
level, like branches on a tree? Those aren't a problem. And you don't 
need them to be tail-recursive, though some languages can optimize those 
into a more efficient iterative form automatically.
Here's a very simple proof: computer processors are iterative. Recursive 
functions are mimicked by using a chunk of memory as a stack. Turing 
machines are iterative, and I've never heard of a recursive function 
that could not be represented with a Turing machine.


> > However, the recursive version is often much simpler, 
> 
> I agree, but it depends on how you look at it.  For people
> not too familiar with the concept, an iterative function
> is far easier to grasp. - And, as I mentioned before, it's
> faster (and more efficient) in almost every case

Conceptually, a recursive definition is the most accurate description of 
many fractals, including the Mandelbrot set. Fractals come out naturally 
from recursive functions, but not from iterative ones. For example, the 
Mandelbrot set's mathematical definition:
z -> z^2 + c


> (Note that I speak as a programmer here, not as a mathematician).

Well, mathematically, iteration is a subset of recursion. In practical 
computer programming though, recursion is done with stacks and iteration.


>  > and most fractals are mathematically defined as recursive
>  > because of the self-similar nature of fractals.
> 
> Can you elaborate on this kind of definition?

http://www.wikipedia.org/w/wiki.phtml?search=fractal&go=Go
http://www.everything2.com/index.pl?node=fractal
http://www.fractalwisdom.com/FractalWisdom/fractal.html
http://www.google.com/ (just search for anything involving "fractal" and 
"recursive" or "recursion")

More info:
http://mathworld.wolfram.com/MandelbrotSet.html
http://mathworld.wolfram.com/Fractal.html


>    I don't doubt this, I just think that one can as well
> define them by iterative means ("As long as the conditions
> are not fulfilled, do repeat...").

As I've said, the recursive version is often much cleaner and simpler. 
Just look at a few examples. The iterative version can be faster to 
compute (especially when function calls are computationally expensive), 
but is usually derived from a recursive mathematical definition.


>    However, I doubt that the relation between recursion and
> self-similarity is as strong as you think.  Recursion is
> often (ab-)used in order to make code look slick, when in
> fact it isn't.

Look at pretty much anything ever written about fractals. The 
relationship between fractals and recursion predates computers. 
Mandelbrot and Leibniz used the exact term "recursive self similarity" 
to describe these shapes. Recursion is very, very important in the 
mathematics of fractals.


> You mean "does not support loops" because there is no
> proper stack to store (local) variables on?  In this
> case, yes; but I'd prefer to solve (not "imitate") this
> by implementing one - *if* I *really* need to... ;)

It has nothing to do with a stack...you don't need that for loops anyway 
(though the POV-Ray function VM does have one). There is no loop 
construct for functions, making iterative functions very awkward to do. 
You can use a chain of select() calls, but that limits complexity, is 
inefficient, and can only be done when you have a fairly small known 
maximum number of iterations. (infinite loops aren't possible)


> BTW, Christopher, what is your profession?

College student. Majoring in computer science (applied mathmatics), 
minoring in physics.

-- 
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