Recursive character counting

I've been having all kinds of trouble figuring out how to count a specific character through a recursive function (I can do it fine through iteration...) but the assignment requires recursion. I know my logic is way off but this is what I have so far...

1
2
3
4
5
6
7
8
9
10
int  countCharR(const char * p, char lookFor)
{
    int count = 0;
    if (*p == NULL) return 0;
    if (*p == lookFor) count++;
    return countCharR(p+1, lookFor);
    
    
    return count;
}
Think of how recursion is breaking down your problem at each step. First of all, I assume your const char* p refers to a null-terminated string. In this problem, it looks like your terminating case is "I've reached the null terminator. When this happens, I return 0." You have a line that does this: if (*p == NULL) return 0;

What happens otherwise? It looks like what you want to do is examine the first character and see if it matches the one you're looking for. You have a line that does this as well:
if (*p == lookFor) count++; However, "count++;" doesn't really express what you're trying to say with this part. We'll come back to this.

You're also trying to express "Now that I've considered the first character, I'll use this same function to evaluate the rest of the string." That's about what this line does: return countCharR(p+1, lookFor);

Where you seemed to get mixed up is trying to maintain some variable called 'count' which only has scope within each function invocation, not throughout every single time you make the recursive call. What you really wish to express is:
1. If I've reached the null terminator, return 0.
2. If the first character is a match, then I want to return however many matches are in the rest of the string PLUS ONE to account for the match I've found here.
3. If the first character is not a match, then this character has no bearing on how many matches there are, so I should just return however many matches are in the rest of the string.
I guess what I'm having a hard time with is how to increment something to keep the count, I realize now that count obviously resets itself every time the function is called. I can recursively run through the string until NULL but I have no idea how to track the matches.
The number of matches in the string p is the number of matches in the string at p+1, plus 1 or 0, depending on whether the character at p is a match.
I feel like an idiot but I still don't see how to iterate...

1
2
3
4
5
6
7
8
9
10
11
int  countCharR(const char * p, char lookFor)
{
    
    if (*p == NULL) return 0;
    if (*p == lookFor) {
        ???????; //
    }
    return countCharR(p+1, lookFor);
    
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;

int globalV=0;

int  countChar(char *p)
{
    
  if (*p)
    {
      cout << *p << "\n";
      globalV++;
      return countChar(p+1);
    } 

  else
    {
      cout << "\nlength = " << globalV << endl;
      return 0;
    }
     
    
}

int main()
{
  char line[] = "hello world";
  char *ch = line;
  countChar(ch);
		
  return 0;	  
}
Last edited on
eladge, line 6 of your last post should be replaced by
return 1+countCharR(p+1, lookFor);
Ahhhh thank you dhayden, I forgot to call the function again if it actually found a match!
Topic archived. No new replies allowed.