Authors:
Walter Savitch ,kenrick Mock
Chapter:
Recursion
Exercise:
Programming Projects
Question:11 | ISBN:9780132846813 | Edition: 5
Question
Write a recursive function named contains with the following header:
bool contains ( char *haystack, char *needle)
The function should return true if the C-string needle is contained within the
C-string haystack and false if needle is not in haystack . For example,
contains("C++ programming", "ogra") should return true
contains("C++ programming", "grammy") should return false
You are not allowed to use the string class substr or find functions to determine
a match.
Answer
PROGRAM CODE:
//Header section
#include <iostream>
#include<cstring>
using namespace std;
// Recursive function to check if the needle is contained within the haystack
bool contains(const char* haystack, const char* needle) {
// Base case: if needle is an empty string, it is always contained
if (*needle == '\0')
{
return true;
}
// Base case: if haystack is an empty string or smaller than needle, needle is not contained
if (*haystack == '\0' || strlen(haystack) < strlen(needle)) {
return false;
}
// Check if the current characters in haystack and needle match
if (*haystack == *needle) {
// Recur for the next character in haystack and needle
return contains(haystack + 1, needle + 1);
} else {
// Recur for the next character in haystack only
return contains(haystack + 1, needle);
}
}
int main()
{
//Initialize the variables
const char* haystack1 = "C++ programming";
const char* needle1 = "ogra";
const char* haystack2 = "C++ programming";
const char* needle2 = "grammy";
//Verify the methods
if (contains(haystack1, needle1))
{
cout << "The needle is contained in the haystack." << endl;
} else {
cout << "The needle is NOT contained in the haystack." << endl;
}
if (contains(haystack2, needle2))
{
cout << "The needle is contained in the haystack." << endl;
} else {
cout << "The needle is NOT contained in the haystack." << endl;
}
return 0;
}
OUTPUT:
The needle is contained in the haystack.
The needle is NOT contained in the haystack.