Counting certain characters in recursion

This is a discussion on Counting certain characters in recursion within the C++ Programming forums, part of the General Programming Boards category; Hey, I'm trying to write a function that uses recursion to count the number of w characters within a group ...

  1. #1
    Registered User
    Join Date
    Oct 2009
    Posts
    2

    Post Counting certain characters in recursion

    Hey, I'm trying to write a function that uses recursion to count the number of w characters within a group in an array.

    wbbwwbww
    bbbbwbww
    wwwbbwww
    wbwbwwbb
    wbwwwbwb
    wbbbbwww
    wbwbbwww
    wbwbbwww

    For the first group, there is only 1, the second has 3, and etc. I've made a few attempts that either cannot count all of the characters, count the same area twice, or run an infinite loop.

    Any help is appreciated.

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Post your code.

  3. #3
    Registered User
    Join Date
    Oct 2009
    Posts
    2
    Code:
    int Process(char spaces[][8], int counter, int &group, int x, int y)
    {
              if(spaces[x][y] == "w")
              {
                   counter++
                   if(spaces[x+1][y] == "w")
                   {
                   spaces[x][y] = "b";
                   return Process(spaces[x][y], counter, group, ++x, y);
                   }
                   if(spaces[x-1][y] == "w")
                   {
                   spaces[x][y] = "b";
                   return Process(spaces[x][y], counter, group, --x, y);
                   }
                   if(spaces[x][y+1] == "w")
                   {
                   spaces[x][y] = "b";
                   return Process(spaces[x][y], counter, group, x, ++y);
                   }
                   if(spaces[x][y-1] == "w")
                   {
                   spaces[x][y] = "b";
                   return Process(spaces[x][y], counter, group, ++x, --y);
                   }
              }
              
              else if(x == 8)
              {
                  ++y;
                  x = 0;
                  return Process(spaces[x][y], counter, group, x, y);
              }
              
              else if(y == 8)
              {
                   return 1;
              }
              
              else
              {
                  ++group;
                  cout << counter;
                  return Process(spaces[++x][y], counter, group, x, y);
              }
    }

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    That's quite a mess, yes.

    1) "w" is a (pointer to a) string literal, and anyway can't be compared with ==. The correct literal would be char, eg: 'w'.

    2) Break things up into small, well defined functions. Maybe start with:

    void update_counters( char* line, size_t length, int& w_counter, int& b_counter );

    Note that the function could be either called within a loop or in some recursive function. Point is, the internal logic wouldn't need to change.

    3) Why are you jumping both forward and backward into the string? That's just a recipe for disaster. Just move forward (starting at zero, of course) to simplify things.

    4) Perform the bounds checking (8, in this case) *before* you actually process the character. Reason being that if the strings are not null terminated (and in this case, they appear not to be) you'll actually wrap around to the next line, which will just botch your results. And anyway, it's just good form to check bounds before anything else.

    5) I'm not really clear what your overall tactic here is, but I think it's safe to say that only one recursive call within the function should be sufficient.

  5. #5
    Professional Chef leeor_net's Avatar
    Join Date
    Apr 2004
    Location
    Charles Town, WV
    Posts
    147
    As you're using C++, why not use strings and stringstream's? I'm no expert in properly using these but they've been instrumental in processing strings and are far easier to work with than the standard C's string functions like strstr() and strcmp(). They're also a lot safer to use in terms of memory allocations and cleanup not to mention dangling pointers and all kinds of other nasty business involved with pointers.

    This, of course, is assuming that your requirements are flexible enough to allow for the use of a different solution to the same problem.
    - Leeor

  6. #6
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    They're also a lot safer to use in terms of memory allocations and cleanup not to mention dangling pointers and all kinds of other nasty business involved with pointers.
    That is not a valid argument for using/not using strings or stringstream. C++ programmers should already know how to deal with memory and pointers.

    The argument for using strings over arrays is simply ease of use and concatenation. The argument for using stringstream over string is that you can treat the stringstream as any other stream and therefore concatenation and string building becomes a snap. The stringstream can also be converted into a string which can then be converted to a C array-style string so it can be used in functions that require those types.

    Beware of stringstream in MSVC 2003 and MSVC 2005. 2005 was known to have a leak in it prior to SP1 and I'm almost positive I have enough evidence to support the claim that 2003 has the same leak.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 09-16-2009, 07:00 AM
  2. Counting the characters from each word from a text file
    By flipguy_ph in forum C Programming
    Replies: 6
    Last Post: 04-27-2009, 06:56 PM
  3. Replies: 10
    Last Post: 07-10-2008, 04:45 PM
  4. Help with hw problem: counting characters in a string
    By pinkfloyd4ever in forum C++ Programming
    Replies: 11
    Last Post: 11-04-2007, 11:18 PM
  5. help with text input
    By Alphawaves in forum C Programming
    Replies: 8
    Last Post: 04-08-2007, 05:54 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21