Subj : Re: Are recursive functions ever needed?
To   : comp.programming
From : Thomas G. Marshall
Date : Mon Oct 03 2005 04:31 am

DarkD coughed up:
>> Well, my problem here seems to be lack of good examples where
>> recursion is needed. Would anybody provide some?
>
> Its used alot in gaming for path finding. Consider a 2x2 array of
> data. A sprite in the game can move 6 'units'. each index in the
> array has a number which is how many units it costs to move over that
> terrain. So you want to create the possible movement area for the
> sprite. You call a function with the x y array index's of the
> position of the sprite, take the terrain value off it and recall the
> same function for the 4 surrouding array values (up down left right)
> etc. so you keep recursively calling and each recursion takes the
> terrain value off its passed value. If it reaches zero that
> recurrsion does't continue. Since you don't actually know how many
> you will do recursion is the only way to do this.

No.  "recursion" means for the call itself to "recur", as in calling itself. 
This is never a requirement, since the stack that you use for these calls 
can be created by hand and dedicated to the problem.

If "recursion" means for the algorithm itself to "recur" (with or without a 
self-call), then you would be right.

I used to draw fractals all the time in BASIC on my Atari-800 back ~1985. 
Had to (of course) invent my own "stack"-like way of saving data, but it all 
worked just fine.  The result was a crafy, yet ugly, iterative solution.



> This kind of
> routine will find the optimal path around any maze etc also, but its
> very cpu intensive and almost impossible to do non recursively.
>
> Use it all the time in games where you pick a unit and its movement
> range comes up and that range is inhibited by trees/mountains/other
> units etc. If anyoone else knows a better way to do this I would be
> very interested.



-- 
Having a dog that is a purebred does not qualify it for breeding.  Dogs
need to have several generations of clearances for various illnesses
before being bred.  If you are breeding dogs without taking care as to
the genetic quality of the dog (again, being purebred is *not* enough),
you are what is known as a "backyard breeder" and are part of the
problem.  Most of the congenital problems of present day dogs are
traceable directly to backyard breeding.  Spay or neuter your pet
responsibly, and don't just think that you're somehow the exception and
can breed a dog without taking the care described.

.