tags:

views:

116

answers:

3

I've written the code below to calculate the length of a word at the beginning of a string with recursion. I've thought of a case in which my code would not work " #@*hello " what do I need to modify the code to resolve this problem (the correct answer is 5)? Thanks

   int startWordLenRec(char s[]) {
        int length;
        if (isLetter(s[0]) == false){
         return 0;
        }
        else{
         length = 1 + startWordLenRec(s+1);
        }
        return length;
    }
A: 

This definitely seems like homework following your previous question on the same code. Please tag it as such.

dajobe
+3  A: 

It's a little unclear why you're using recursion outside a functional language to solve this problem. It's also, frankly, a little unclear what the actual parameters of the problem are.

If your actual intention is to measure the length of the first word in the string (defined as a sequence of characters that return a True result if passed to isLetter) even if that word does not start at the beginning of the string, then the simplest, clearest solution seems to be: make the function take a flag as an argument, called letterSeenYet. On the initial call to the function, the flag should be set to False.

  • If the function reads a non-letter character, and the letterSeenYet flag is False, set length equal to 0 + the results of the recursive function call, and make sure the flag on that call is set to False.
  • If the function reads a letter character, set length equal to 1 + the results of the recursive function call, and make sure the flag on that call is set to True.
  • If the function reads a non-letter character, and the letterSeenYet flag is True, return 0.

I hope you see the logic: you want a non-letter character to mean "stop counting letters", but only after you've seen some letters to begin with.

Again, I really don't understand why you're using recursion for this problem. There are some problems that are easier to comprehend in their recursive form, but this one seems far, far easier (and more efficient) to handle iteratively. (Also, as Charles Salvia points out, you should be prepared not just for the end of the first word, but for the possible end of the string.)

A: 

Thinking in terms of recursion can be a little tricky. Without going into the details as to why or why not to use recursion, let's assume it has to be recursion (homework, discovery, whatever the reason).

So the main thing to consider for recursion is what the terminating condition is. If you have trouble doing so, maybe writing the algorithm in an iterative fashion can help you.

In this instance, what you need to determine is when the character array ends. This will be the case if the current character is '\0'.

A simple recursive algorithm might be:

  • Check current character. Is it '\0' ?
    • Yes: Return 0
    • No. Is the current character a letter?
      • Yes: return 1 + call this function with incremented character pointer
      • No: return 0 + call this function with incremented character pointer

Note that this algorithm will not terminate after seeing a non-letter character, so " test a" will return 5, not 4. If you have to terminate before, you would need some type of flag, that gets passed to the function.

Anyway, my main point was to think of what the terminating condition should be.

JRL