Sometimes you can find a solution to the original problem by defining a recursive function to a problem similar to the original problem. This new function is called a recursive helper function. The original problem can be solved by invoking the recursive helper function.
The preceding recursive isPalindrome function is not efficient, because it creates a new string for every recursive call. To avoid creating new strings, you can use the low and high indices to indicate the range of the substring. These two indices must be passed to the recursive function. Since the original function is isPalindrome(const string& s), you have to create a new function isPalindrome(const string& s, int low, int high) to accept additional information on the string, as shown in Listing 17.4.
Listing 17.4 RecursivePalindromeUsingHelperFunction.cpp
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 bool isPalindrome(const string& s, int low, int high)
6 {
7 if (high <= low) // Base case
8 return true;
9 else if (s[low] != s[high]) // Base case
10 return false;
11 else
12 return isPalindrome(s, low + 1, high – 1);
13 }
14
15 bool isPalindrome(const string& s)
16 {
17 return isPalindrome(s, 0, s.size() – 1);
18 }
19
20 int main()
21 {
22 cout << “Enter a string: “;
23 string s;
24 getline(cin, s);
25
26 if (isPalindrome(s))
27 cout << s << ” is a palindrome” << endl;
28 else
29 cout << s << ” is not a palindrome” << endl;
30
31 return 0;
32 }
Two overloaded isPalindrome functions are defined. The function isPalin drome(const string& s) (line 15) checks whether a string is a palindrome, and the second function isPalindrome(const string& s, int low, int high) (line 5) checks whether a substring s(low..high) is a palindrome. The first function passes the string s with low = 0 and high = s.size() – 1 to the second function. The second function can be invoked recursively to check a palindrome in an ever-shrinking substring. It is a common design technique in recursive programming to define a second function that receives additional parameters. Such a function is known as a recursive helper function.
Helper functions are very useful to design recursive solutions for problems involving strings and arrays. The sections that follow present two more examples.
1. Selection Sort
Selection sort was introduced in Section 7.10, “Sorting Arrays.” Now we introduce a recursive selection sort for characters in a string. A variation of selection sort works as follows. It finds the largest element in the list and places it last. It then finds the largest element remaining and places it next to last, and so on until the list contains only a single element. The problem can be divided into two subproblems:
- Find the largest element in the list and swap it with the last element.
- Ignore the last element and sort the remaining smaller list recursively.
The base case is that the list contains only one element.
Listing 17.5 gives the recursive sort function.
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 void sort(string& s, int high)
6 {
7 if (high > 0)
8 {
9 // Find the largest element and its index
10 int indexOfMax = 0;
11 char max = s[0];
12 for (int i = 1; i <= high; i++)
13 {
14 if (s[i] > max)
15 {
16 max = s[i];
17 indexOfMax = i;
18 }
19 }
20
21 // Swap the largest with the last element in the list
22 s[indexOfMax] = s[high];
23 s[high] = max;
24
25 // Sort the remaining list
26 sort(s, high – 1);
27 }
28 }
29
30 void sort(string& s)
31 {
32 sort(s, s.size() – 1);
33 }
34
35 int main()
36 {
37 cout << “Enter a string: “;
38 string s;
39 getline(cin, s);
40
41 sort(s);
42
43 cout << “The sorted string is ” << s << endl;
44
45 return 0;
46 }
Two overloaded sort functions are defined. The function sort(string& s) sorts characters in s[0..s.size() – 1] and the second function sort(string& s, int high) sorts characters in s[0..high]. The helper function can be invoked recursively to sort an ever-shrinking substring.
2. Binary Search
Binary search was introduced in Section 7.9.2, “The Binary Search Approach.” For binary search to work, the elements in the array must already be ordered. The binary search first compares the key with the element in the middle of the array. Consider the following cases:
- Case 1: If the key is less than the middle element, recursively search the key in the first half of the array.
- Case 2: If the key is equal to the middle element, the search ends with a match.
- Case 3: If the key is greater than the middle element, recursively search the key in the second half of the array.
Case 1 and Case 3 reduce the search to a smaller list. Case 2 is a base case when there is a match. Another base case is that the search is exhausted without a match. Listing 17.6 gives a clear, simple solution for the binary search problem using recursion.
Listing 17.6 RecursiveBinarySearch.cpp
1 #include <iostream>
2 using namespace std;
3
4 int binarySearch(const int list[], int key, int low, int high)
5 {
6 if (low > high) // The list has been exhausted without a match
7 return -low – 1; // key not found, return the insertion point
8
9 int mid = (low + high) / 2;
10 if (key < list[mid])
11 return binarySearch(list, key, low, mid – 1);
12 else if (key == list[mid])
13 return mid;
14 else
15 return binarySearch(list, key, mid + 1, high);
16 }
17
18 int binarySearch(const int list[], int key, int size)
19 {
20 int low = 0;
21 int high = size – 1;
22 return binarySearch(list, key, low, high);
23 }
24
25 int main()
26 {
27 int list[] = { 2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79};
28 int i = binarySearch(list, 2, 13); // Returns 0
29 int j = binarySearch(list, 11, 13); // Returns 4
30 int k = binarySearch(list, 12, 13); // Returns –6
31
32 cout << “binarySearch(list, 2, 13) returns ” << i << endl;
33 cout << “binarySearch(list, 11, 13) returns ” << j << endl;
34 cout << “binarySearch(list, 12, 13) returns ” << k << endl;
35
36 return 0;
37 }
Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.