Subj : Re: Are recursive functions ever needed?
To   : comp.programming
From : Gerry Quinn
Date : Mon Oct 03 2005 11:19 am

In article <433f33c2$0$21879$afc38c87@news.optusnet.com.au>, 
darkd@NOSPAMoptusworld.com.SPAM.au says...
> 
> > 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. 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.

There are two issues.  One is whether the method is essentially 
recursive in nature, and this is.  It goes back on itself, repeating 
the same process on the data resulting from the previous iteration.  
I'd call it a recursive method, however it is implemented.

The other is whether some explicit sort of recursion is needed, i.e. 
whether there must be a function that directly or indirectly calls 
itself.  In essence, this is never really needed in normal imperative 
languages, and when used is usually - but not always - bad.

The case above is an example of one in which explicit recusion is 
generally bad unless it is known that the length of the path is going 
to be short.  Actually it's a special form of a much more common 
problem which is 'can this object reach a particular square and if so 
what is the path to it'.  If the square can be a long distance away, it 
is vastly more efficient to use a working array corresponding to the 
game map with a check value for each position, and carry out the 
calculation in an explicitly iterative form.

Using a pure recursive method involves keeping a list of positions and 
check values, and when this list becomes large there is a significant 
time overhead, because it is necessary to search it at every stage to 
determine whether a position has been reached before.  Having a check 
array involves an initial investment in space, but is much more time-
efficient.  And by keeping a list of the modified squares, the check 
array can be wiped efficiently in preparation for the next calculation.  
(Of course it's not intrinsically thread safe, if that matters.)  
 
- Gerry Quinn


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

.