 Recursive Word Reversal
This function prints out the words in a sentence reversed. The function uses recursive calls to itself. The definition of words is any sequence of characters delimited by one or more spaces. The resulting printout should include only one space between words, with no spaces before the first word or after the last word. Therefore, the input string can have multiple spaces between words, or before and after the string, but the result should not preserve those.
The bug does not involve the stack potentially overflowing because of excessive recursion-assume that is not an issue.
For this example, the length of the string is passed as an argument; thus, the string is not assumed to be terminated with a '\0' character. This is primarily done to make the recursion easier because it allows the recursive function calls to also specify the length of the string explicitly. Thus, it can operate on a substring of the original string without modifying or copying the string to put a final '\0' in.
The function uses the C standard library function printf() to display the string. The relevant syntax is
printf ("%.*s", n, s);
n represents a number and s is a string. This prints out the first n characters of the string s (unless s terminates earlier with a '\0'). The function can also print out a '\0'-terminated string, with no length needed:
printf ("%s", s);
or print out a literal string:
printf ("Hello");
but this example doesn't use it that way.
Source Code
1. void
2. print_reversed_string(
3. char * inp_str,
4. int inp_str_length) {
5.
6. // Go to the end of the string and walk backwards.
7. // When we hit the start of a word, print it, then
8. // call recursively on the preceding part.
9.
10. char * current_character;
11. char * end_of_word;
12.
13. // First skip any blanks at the end.
14.
15. current_character = inp_str + (inp_str_length-1);
16. while (current_character >= inp_str) {
17. if (*current_character != ' ') break;
18. --current_character;
19. }
20.
21. if (current_character >= inp_str) {
22.
23. // end_of_word points to last char in the word.
24. end_of_word = current_character;
25.
26. // Now go back and find the beginning of the
27. // word. We know the current is non-blank so we
28. // can back up one right away.
29. --current_character;
30. while (current_character >= inp_str) {
31. if (*current_character == ' ') break;
32. --current_character;
33. }
34.
35. // current_character now points one character
36. // before the beginning of the word -- either
37. // a blank, or one byte before inp_str.
38.
39. printf ("%.*s",
40. end_of_word - current_character,
41. current_character + 1);
42.
43. if (current_character >= inp_str) {
44.
45. // If there is more before this, then
46. // print a separator and call recursively,
47. // passing the previous part of the string.
48. printf(" ");
49. print_reversed_string(
50. inp_str,
51. (current_character+1) - inp_str);
52. }
53. }
54. }
Suggestions
This function calls itself recursively. Under what conditions does it exit instead of making the recursive call? What guarantees are there that it will not get into an infinite set of recursive calls (by calling itself recursively with the exact same parameters that it was passed)? What different types of inputs would the function need to ensure that every line of code is executed? What is the useful lifetime of current_character as compared to end_of_word? The calculation on line 51 is not obvious. Understand exactly where current_character is in relation to inp_str when this call is made to verify that the calculation is correct.
Hints
Walk through the code with the following parameters to the function:
A good test case is to have spaces at the end of the input string with multiple spaces between words, inp_str == "Hello world ", inp_str_length == 14: inp_str[0] == 'H'
inp_str[1] == 'e'
inp_str[2] == 'l'
inp_str[3] == 'l'
inp_str[4] == 'o'
inp_str[5] == ' '
inp_str[6] == ' '
inp_str[7] == 'w'
inp_str[8] == 'o'
inp_str[9] == 'r'
inp_str[10] == 'l'
inp_str[11] == 'd'
inp_str[12] == ' '
inp_str[13] == ' '
inp_str[14] == '\0'
Test spaces at the beginning of the input string, inp_str == " qwerty uiop", inp_str_length == 12: inp_str[0] == ' '
inp_str[1] == 'q'
inp_str[2] == 'w'
inp_str[3] == 'e'
inp_str[4] == 'r'
inp_str[5] == 't'
inp_str[6] == 'y'
inp_str[7] == ' '
inp_str[8] == 'u'
inp_str[9] == 'i'
inp_str[10] == 'o'
inp_str[11] == 'p'
inp_str[12] == '\0'
Explanation of the Bug
The problem occurs when spaces exist at the beginning of the string. The function is set to print nothing if all it is passed is a string full of spaces. However, at line 48, before the recursive call, it always calls
printf(" ");
Even if the string passed to the recursive call has only spaces and does nothing, the unwanted space still has been printed by line 48. This is a D.limit error.
The second hint shows this behavior. The first time through the function, it will back current_character up to point to inp_str[7]; that is, the space right before the word "uiop". The code prints out "uiop", then prints a space and calls itself recursively as print_reversed_string(inp_str, 8). Inside this recursive call, it backs up current_character to point to inp_str[0], which is the space right before the word "qwerty". It prints out "qwerty", the check on line 43 succeeds (current_character and inp_str will be equal, in fact), so it will print a space-the error in question-then call itself recursively again as print_reversed_string(inp_str, 1). In this last recursive call, the while condition on line 16 becomes false after one iteration, the if on line 21 is false, and the function exits. But, the extra space at the end has been printed.
With the first hint, when current_character moves back to before "Hello", the if on line 43 becomes false, so the extra space won't be printed.
One solution is to strip off the spaces at the end of the string before the recursive call. Between lines 41 and 43, add a repeat of lines 16-19:
while (current_character >= inp_str) {
if (*current_character != ' ') break;
--current_character;
}
This means the code on lines 16-19 only ever finds any spaces to strip on the first outer call to the function; on any recursive call, inp_str_length will have been adjusted back by the newly added code to hide any spaces.
| 
