Recursive question

This is a discussion on Recursive question within the C Programming forums, part of the General Programming Boards category; quick question here, in this recursive function to test a word to see if its a palindrome: Code: int ispalindrome(char ...

  1. #1
    Registered User
    Join Date
    Feb 2006
    Location
    North Liberty, IA
    Posts
    67

    Recursive question

    quick question here, in this recursive function to test a word to see if its a palindrome:


    Code:
    int ispalindrome(char *s, int len)
    {
    	if (len <=1 ) return 1;
    	else return((s[0] == s[len-1]) && ispalindrome(s+1, len-2));
    }


    In one case, an integer: 1 is returned. This means the word is too short. How does the other return statment determine whether it's a palindrome or not, and how do I test it in the main?

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,789
    Code:
    else return((s[0] == s[len-1]) && ispalindrome(s+1, len-2));
    The other path returns the boolean AND of two values, one of which is the comparison of the first (s[0]) and last (s[len-1]) positions of the character array. If this comparison results in false (the two characters are not equal), then the function will return 0 (false); otherwise, the code will continue checking the remainder of the character array by calling the function recursively and passing a shorter version of the array originally passed into it. One possible way you could call it from main is like so:

    Code:
    char * words = "able was I ere I saw elba";
    if( ispalindrome(words,strlen(words)) )
        printf("It is a palindrome.\n");
    else
        printf("It is not a palindrome.\n");
    Let's go through this for the character array "bob": ispalindrome("bob",3);
    1. The first thing we do is check if the length passed in is less than or equal to 1, this is not the case so we continue to the "else" portion of the function.
    2. We now check the result of s[0] (b) == s[2] (b) which is true.
    3. Since step 2 was true, we must also check the result of the call of ispalindrome("o",1). (If step 2 was false/0 then the rest of the statement, the recursive portion, would NOT be called).
    3.1. In the second instance of the call, the length is less than or equal to 1 and so we return true/1 immediately.
    4. The value returned from the second call (step 3.1) is 1 which gets AND'ed with the true/1 result we already got from the comparison in step 2 and so we return a final value of 1(true).

    Now, let's go through this for the character array "abba": ispalindrome("abba",4);
    1. Length is not <= 1 so continue with the "else" portion of the function.
    2. s[0] (a) == s[3] (a) is true/1 so now must call the function recursively.
    3. Call ispalindrome a second time with ("bb",2) as arguments.
    3.1 Length is not <= 1 so continue with the "else" portion of the function
    3.2 s[0] (b) == s[1] (b) so now must call the function recursively.
    3.3 Call ispalindrome a third time with ("",0) as arguments.
    3.3.1 Length is <= 1 so return true/1 immediately exiting third call to function.
    3.4 Return true/1 (step 3.2) AND true/1 (step 3.3.1), this is the return from the second call to the function
    4. Return true/1 from step 2 AND true/1 from step 3.4 to give an overall result of true/1.

    Now, let's go through this for the character array "abca": ispalindrome("abca",4);
    1. Length is not <= 1 so continue with the "else" portion of the function.
    2. s[0] (a) == s[3] (a) is true/1 so now must call the function recursively.
    3. Call ispalindrome a second time with ("bc",2) as arguments.
    3.1 Length is not <= 1 so continue with the "else" portion of the function
    3.2 s[0] (b) == s[1] (c) is false so return false/0 immediately and do not call function recursively.
    4. Return true/1 from step 2 AND false/0 from step 3.2 to give an overall result of false/0.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    I wouldn't intepret that as word is too short, I'd intepret either as a sinlgle letter word is a palidrome or as we reached the middle of the word/phrase, with either 1 or 0 letters left, and since we made it this far, it must be a palidrome, return 1 which gets interpreted as true;

    If we hadn't made it that fare we would had already returned 0 which can be interpreted as false

  4. #4
    Registered User
    Join Date
    Feb 2006
    Location
    North Liberty, IA
    Posts
    67
    That was an absoulety wonderful explanation. Thank you very much.
    I wondered how that worked for sure, and now I know. Thanks again!!!!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. transforming this loop into a recursive function question
    By transgalactic2 in forum C Programming
    Replies: 17
    Last Post: 01-22-2009, 04:11 AM
  2. Replies: 15
    Last Post: 12-13-2008, 08:32 AM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  5. opengl DC question
    By SAMSAM in forum Game Programming
    Replies: 6
    Last Post: 02-26-2003, 08:22 PM

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