Thread: problem with recursion and string

  1. #1
    Registered User
    Join Date
    Nov 2009
    Location
    Italy
    Posts
    65

    problem with recursion and string

    hi guys, i need help with this algorithm, given a string and a character, the function char *lastocc(char *s, char c) has to return a pointer to the last occurrence of the character c in the string *s, for example if the word is swimming and the char is i it shoud return ' ing ', here's what i wrote:
    Code:
    char *lastocc(char *s, char c)
    {
    	if(*s == '\0') {
    		return;
    	}
    	else if(*s != c) {
    		*lastocc(s+1, c);
    	}
    	else if(*s == c) {
    		printf("%s", s);
    		*lastocc(s+1, c);		
    	}
    	
    }
    the problem is that it returns every occurrence of the character (hence imming and ing) while it should return only the last one, i still cant figure out how to do that, any suggestion?
    Last edited by rob90; 12-09-2009 at 03:31 PM.

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    There's already a function that does that in standard C. You could just write the function as:
    Code:
    char *lastocc(char *s, char c)
    {
      return strrchr(s, c);
    }
    However, if you want to re-invent the wheel, you're going to have to at least return a value. I don't see how the code you posted is compiling cleanly, let alone returning anything.
    If you understand what you're doing, you're not learning anything.

  3. #3
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    You will also need to loop through your array of char, *s, preferably via a while loop. Then while your doing that, inspecting each char that matches to (c). Then either return that pointer position of the string (*s) or the index value as needed.

  4. #4
    Registered User
    Join Date
    Nov 2009
    Location
    Italy
    Posts
    65
    Quote Originally Posted by itsme86 View Post
    There's already a function that does that in standard C. You could just write the function as:
    Code:
    char *lastocc(char *s, char c)
    {
      return strrchr(s, c);
    }
    However, if you want to re-invent the wheel, you're going to have to at least return a value. I don't see how the code you posted is compiling cleanly, let alone returning anything.
    yes, it didnt return anything because i wanted to see what was happening through the printf, anyway i need to do this without using any other function..
    Code:
    char *function(char *s, char c)
    {
    	if(*s == '\0') {
    		return;
    	}
    	else if(*s != c) {
    		return function(s+1, c);
    	}
    	else if(*s == c) {
    		return s;		
    	}	
    }
    this returns the the first occurence of the character, i cant find a way to make it find the last..
    Last edited by rob90; 12-09-2009 at 04:10 PM.

  5. #5
    Registered User
    Join Date
    Nov 2009
    Location
    Italy
    Posts
    65
    Quote Originally Posted by slingerland3g View Post
    You will also need to loop through your array of char, *s, preferably via a while loop. Then while your doing that, inspecting each char that matches to (c). Then either return that pointer position of the string (*s) or the index value as needed.
    i need to do it in a recursive way, not by iteration

  6. #6
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    You should implement some counter variable then and tie this into the pointer position to return.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    this returns the the first occurence of the character, i cant find a way to make it find the last..
    Instead of starting at the first char in the string, start at the last, and decrement, instead of increment as you recurse through the function.

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Strings are bunches of characters side by side in memory. Just like an array, the lowest value is first.
    Code:
    char *srevc( char *s, int c )
    {
        if( s && *s )
        {
            char *p = srevc( s+1, c );
            s = p && *p == c ? p : *s == c ? s : NULL;
        }
        return s;
    }
    It's best if you can explain what it does before you turn it in some place.

    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Registered User
    Join Date
    Nov 2009
    Location
    Italy
    Posts
    65
    Quote Originally Posted by quzah View Post
    Strings are bunches of characters side by side in memory. Just like an array, the lowest value is first.
    Code:
    char *srevc( char *s, int c )
    {
        if( s && *s )
        {
            char *p = srevc( s+1, c );
            s = p && *p == c ? p : *s == c ? s : NULL;
        }
        return s;
    }
    It's best if you can explain what it does before you turn it in some place.

    Quzah.
    thanks

  10. #10
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    If they have not covered the tertiary operator s/he is in trouble! Nice trick, I have not even come close to devising that strategy.

  11. #11
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    There are quite a few problems with the posted code, as in

    Invoking the function as *lastocc() instead of lastocc(), and
    Not storing the return value of lastocc() someplace, and lastly
    Not returning NULL when the end of the string is reached.

    lastocc() will give correct results after resolving the above issues.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Another String Problem
    By w2look in forum C Programming
    Replies: 6
    Last Post: 02-25-2009, 12:00 PM
  2. String (?) Recursion
    By Lansan1ty in forum C++ Programming
    Replies: 5
    Last Post: 11-20-2008, 04:43 PM
  3. recursion error
    By cchallenged in forum C Programming
    Replies: 2
    Last Post: 12-18-2006, 09:15 AM
  4. Problem creating a recursive string permutation function
    By indigo0086 in forum C++ Programming
    Replies: 4
    Last Post: 10-10-2006, 10:09 AM
  5. convert string into integer using recursion
    By peter_hii in forum C++ Programming
    Replies: 18
    Last Post: 08-23-2006, 10:09 AM