Thread: Recursive question

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.