Recursion

[Thrillhouse]

I'm a college computer science major and I'm studying for my final exam by
going over previous tests. There's one question that I answered correctly
but I cannot, for the life of me, figure out how it works. The machine I'm
currently on does not have any environment or compiler so I can't test it.
The question was to write a recursive function that's passed a char pointer
and returns the maximum valued character in the string. Here's what I
wrote:
char maxChar(char *s)
{
char c;
if(*s == '\0')
return *s;
c = maxChar(++s);
if(c>*s)
return c;
else
return *s;
}

Can somebody explain to me how this works? How can maxChar return the
largest valued character to the first call of it if it can never reach the
if-else until the end of the string? I know it sounds stupid but I'm truly
dumbfounded by it. Thanks for the help.

 

[Dave Townsend]

I'm a college computer science major and I'm studying for my final exam by
going over previous tests. There's one question that I answered correctly
but I cannot, for the life of me, figure out how it works. The machine I'm
currently on does not have any environment or compiler so I can't test it.
The question was to write a recursive function that's passed a char pointer
and returns the maximum valued character in the string. Here's what I
wrote:
char maxChar(char *s)
{
char c;
if(*s == '\0')
return *s;
c = maxChar(++s);
if(c>*s)
return c;
else
return *s;
}

Can somebody explain to me how this works? How can maxChar return the
largest valued character to the first call of it if it can never reach the
if-else until the end of the string? I know it sounds stupid but I'm truly
dumbfounded by it. Thanks for the help.

Your code has a bug in it which your professor must have missed, shame on
him!.
If you pass a string where the first character is the max character, your
function
will miss it!

Try this - here I've saved the first character of the string before
incrementing s.

char maxChar(char *s)
{
char c;
char max;
if(*s == '\0')
return *s;
max = *s;
c = maxChar(++s);
if(c>max)
return c;
else
return max;
}

The reasoning behind this algorithm is as follows. Take the first character
of
the string and pass the remaining characters to maxChar recursively.
Compare
the results, choose the max and return that. If a string is empty, then 0
is the max
char value.

 

[B.C.]

I think you have to think in terms of induction. Assuming the string is null
terminated:

if the string is empty (in c terms it means the only char of the string is
the null char) then max(string) is 0
otherwise
max (string) = max between the first character of the string and max
(string without the first character) so:

#include <stdio.h>

char maxChar(char* s)
{
char c;
if (*s == 0)
return 0;
c = maxChar(s + 1);
return c >= *s ? c: *s;
}

int main(int argc, char** argv)
{
printf("%c\n", maxChar("FRCZOP"));
return 0;
}

It will print Z

Your program is not working correctly because you increment s. If you call
your maxChar, maxChar("ZFRCOP") will print R and not Z and this is because
you increment s.

 

[Thomas Wintschel]

I'm a college computer science major and I'm studying for my final exam by
going over previous tests. There's one question that I answered correctly
but I cannot, for the life of me, figure out how it works. The machine I'm
currently on does not have any environment or compiler so I can't test it.
The question was to write a recursive function that's passed a char pointer
and returns the maximum valued character in the string. Here's what I
wrote:
char maxChar(char *s)
{
char c;
if(*s == '\0')
return *s;
c = maxChar(++s);
if(c>*s)
return c;
else
return *s;
}

Can somebody explain to me how this works? How can maxChar return the
largest valued character to the first call of it if it can never reach the
if-else until the end of the string? I know it sounds stupid but I'm truly
dumbfounded by it. Thanks for the help.

I refuse to be too helpful since this could be home work (and in any
case you acknowledge copying it from someone else's previous answer) but
I will ooffer a hint.

You ask "How can maxChar return the largest valued character to the
first call of it if it can never reach the if-else until the end of the
string?"

Note that the function is recursive. That is, it calls itself. The
first call to it that returns IS the call that handles the end of the
string. The string is effectively processed from the end (although an
explicit call to it requires a pointer to the beginning). Try stepping
through it in your head with the string "ab".

Out of curiosity, why is it that a computer science major has no access
to a build envirionment/compiler?

 

[Thrillhouse]

Thanks for all the help.
The reason I don't have access to an environment/compiler is because the
notebook I was working on had beer spilt on it(I am a college student)
coroding the motherboard. I just put in the order for a new computer.
I'm using one of my roommate's computers for school work. Thanks again
for the suggestions.