In article <11**********************@i40g2000cwc.googlegroups .com>,
"andrew browning" <ah**@mac.com> wrote:
if i write a function to find the max value of an array and want to
write it recursively, how do i decide on the base case? i want to say:
if (index 0 is the only index then it is max)
else...
but i think that may be screwy logic.
please advise
The general rule when making a loop recursive is don't. Loops are
usually faster, usually take up less space in RAM, and are usually easer
to understand and modify.
To create a recursive function, first solve for the case where no
recursion is necessary:
int max( int* arr, unsigned sz ) {
int result = arr[0];
return result;
}
Then test to see if recursion is necessary. If it is, change the
variable that you tested against to be one step closer to the proper
value and recall the function:
int max( int* arr, unsigned sz ) {
int result = arr[0];
if ( sz != 1 ) {
--sz;
result = arr[sz] > max( arr, sz ) ? arr[sz] : max( arr, sz );
}
return result;
}
Now compare the above to a loop that does the same thing:
int max( int* arr, unsigned sz ) {
int result = arr[0];
while ( sz != 1 ) {
--sz;
result = arr[sz] > result ? arr[sz] : result;
}
return result;
}
When changing from loop to recursion, the 'while' becomes an 'if' and
the references to the partial result inside the 'while' become recursive
calls inside the 'if'.
Of course, I recommend you use std::max_element instead (which is
implemented as a loop on my system. :-)
--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.
