Recursive code for a palindrome

[Griff0527]

Ok, I have read several other questions basically asking the same thing, but I know this code can work instead of using other peoples work. Yes, i'm stubborn. I have written a function to be called from my main program and i keep getting an error that I cannot figure out. Please look over the below code and see if you can help me determine what is wrong with the line "palindrome(string[1]);". I know it must be something terribly simple, but for some reason, I cannot see it. Any ideas out there? Thanks you to anyone that can assist.

int palindrome(const char *string)
{
    int ans;
    char sub[MAX_LEN];

    if (strlen(string) <= 1) {
        ans = 1;
    } else if (string[0] != string[strlen(string)-1]) {
        ans = 0;
    } else {
         palindrome(string[1]); /* this should be testing for the next element in the array on each pass, compared to the next to last element in the array */

     ans = palindrome(sub);
    }


    return (ans);
}

[WaltP]

palindrome(string[1]);

is passing a single character into the function. You probably want

palindrome(&string[1]);

since that's what the function is expecting.

As for your logic, it's a royal mess. You are expecting the entire string to be available in the function, but never really keep track of the locations you are testing. Based on what I see, you are trying to test each character from the beginning with the last character of the string itself.

To do what you are attempting, you probably need to pass in the string (all of it), 0 (first char position), and strlen(string)-1 (last char position) in the initial call. Then call the itself with string (all of it), incrementing the first position and decrementing the last position.

[Griff0527]

WaltP,
I have changed my code as you suggested, but I think I have created an infinite loop in my recursion. Just for clarification, I am a student in college, and so I know very little about C. However, I am not asking for an "easy answer" here. I want to understand this code and what I am doing wrong. I previously took Java and did extremely well with it, but recursion in C is giving me a headache. I'm comprehending almost everything else in C except for recursion for some reason (words from a n00b coder must be taken lightly when implying understanding as I'm sure looking at my code with verify)...
Lucky me, I have C++ as my next course.

#include <stdio.h>
 #include <string.h>
 #include <ctype.h>

 #define MAX_LEN 50

int
main(void)
{
/* Create variable for string */
char string[MAX_LEN];
int i, k;
/* Create external function */
char palindrome(char *, int, int);

/* Explain purpose of program to user and prompts for input */
printf("This program will test a phrase inputted by you to see\n");
printf("if it is a palindrome.\n\n");
printf("Please enter a word or phrase of no more than 50 characters.\n\n>");


/* Receive input from user and stores it in input_string array */
scanf("%s", string);

/* Call external recursive function, receive the return value, and determine output */

if (palindrome(string, i, k)==1)
            printf("%s is a palindrome.\n",string);
        else
            printf("%s is not a palindrome.\n",string);
}

/* Recursive function to test first char to last char, second to second to last, etc. */


char palindrome (char string[], int i, int k)
{
    int ans;
    k = strlen(string);
    if (k <= 1)
    ans = 1;
    else if (string[i] != string [k-1])
    ans = 0;
    else return palindrome(string, i+1, k-2);

}

Someone please help me in getting this right. Point me in the right direction, give me a hint or a slap-to-the-back-of-the-head.
Thank you.
/Signed/
Newbie to C - Griff0527

[jephthah]

one problem is your function, palindrome, expects two integers to be passed into it. you've declared these integers in main as 'i' and 'k' but you don't assign any value to them before passing them into the call to palindrome. therefore, they will either be zero or some large value of random garbage.

also, your function palindrome, which has two ints being passed as inputs, then completely ignores whatever input you might have passed in for the one called 'k' and assigns a value of string length to it.

you probably want to remove 'int k' from the palindrome function prototype, and declare 'int k' as local variable in palindrome.

this still doesn't fix the fact that you are not passing anything in for 'i' what is the purpose of 'i' what should the 'main()' routine be setting it to, before passing it into the palindrome function.

there are other problems. that's just a start. but it will probably lead you to discover and fix them.

you really should be running this in a debugger, to step through each line and check what the variables are being set to.

[Griff0527]

Speaking of a debugger, I was trying ot sort out how to use the debugger in Code::Blocks v8.02, but couldn't figure it out. i am currently working with your suggestions on the code to see if I get any closer to a resolution to this program. Thank you for the insight and I'll see what I can make of my mess before posting again.

one problem is your function, palindrome, expects two integers to be passed into it. you've declared these integers in main as 'i' and 'k' but you don't assign any value to them before passing them into the call to palindrome. therefore, they will either be zero or some large value of random garbage.

also, your function palindrome, which has two ints being passed as inputs, then completely ignores whatever input you might have passed in for the one called 'k' and assigns a value of string length to it.

you probably want to remove 'int k' from the palindrome function prototype, and declare 'int k' as local variable in palindrome.

this still doesn't fix the fact that you are not passing anything in for 'i' what is the purpose of 'i' what should the 'main()' routine be setting it to, before passing it into the palindrome function.

there are other problems. that's just a start. but it will probably lead you to discover and fix them.

you really should be running this in a debugger, to step through each line and check what the variables are being set to.

[Griff0527]

ok.. been working on and looking at the code since my earlier post today... In all honesty, I'm about ready to give up. I have re-read the chapter 5 times, paying specific attention to all the examples, and I'm stuck. Someone throw a brick at my head please... The error I get in the compiler is "warning: control reaches end of non-void function in function char palindrome(char *, int).

/*
 * Programmer: Cody Griffin
 * Instructor: Matthew Chrenka
 * Class CS263
 * Date Completed April 12, 2010
 *
 * Program recieves String input from the user and determines if the input is a palindrome.
 */

 #include <stdio.h>
 #include <string.h>
 #include <ctype.h>

 #define MAX_LEN 50

int
main(void)
{
/* Create variable for string */
char string[MAX_LEN];
int i = 0; /* initial position of array element */
/* Create external function */
char palindrome(char *, int);

/* Explain purpose of program to user and prompts for input */
printf("This program will test a phrase inputted by you to see\n");
printf("if it is a palindrome.\n\n");
printf("Please enter a word or phrase of no more than 50 characters.\n\n>");


/* Receive input from user and stores it in input_string array */
scanf("%s", string);

/* Call external recursive function, receive the return value, and determine output */

if (palindrome(string, i)==1)
            printf("%s is a palindrome.\n",string);
        else
            printf("%s is not a palindrome.\n",string);
}

/* Recursive function to test first char to last char, second to second to last, etc. */


char palindrome (char string[], int i)
{
    int ans;
    int k = strlen(string);
    if (k <= 1)
    ans = 1;
    else if (string[i] != string [k-1])
    ans = 0;
    else return palindrome(string, i+1);

}

[jephthah]

The error I get in the compiler is "warning: control reaches end of non-void function in function char palindrome(char *, int).

char palindrome (char string[], int i)
{
    int ans;
    int k = strlen(string);

    if (k <= 1)
        ans = 1;
    else if (string[i] != string [k-1])
        ans = 0;
    else 
        return palindrome(string, i+1);

}

well, that's simple. you don't have a return statement for the first two conditions, only for the third. you need to always return.

i reccommend that you should have one and only one return statement at the end of the function, that will always be reached regardless of the conditional branches. \set the various return values in the conditional branches, but don't return until the end.

also notice how i indented your code. you should always indent your code properly. otherwise you can't hardly read the code and will be prone to making these kinds of errors.

another problem i see, is what is "ans"? you're setting this variable in teh function, but it serves no purpose and is neither returned nor passed back to the caller.

.

[jephthah]

okay man, i wrote your palindrome recursive thing, in three lines of code. well, six lines with whitespace. it can be done and it's simple ... once you wrap your head around recursion, which is the hard part.

i'm tempted to give it to you, but I'll be doing you a disservice as you won't learn from that.

so i'll give you the method, laid out in a pseudocodeish example sort of way.

cheers.

in function main()

char* str="annabanna"
int len(str) = 9

call palindrome(char* str, int len);

--->inside palindrome:

         annabanna
         ^       ^
   *str='a'      
   --len=8       str[len]='a'
     ++str
     --len

    call palindrome(str, len);

    --->inside palindrome:

             annabanna
              ^     ^
       *str='n'      
       --len=6       str[len]='n'
         ++str
         --len

        call palindrome(str, len);

        --->inside palindrome:

                 annabanna
                   ^   ^
           *str='n'      
           --len=4       str[len]='n'
             ++str
             --len


            call palindrome(str, len);

            --->inside palindrome:

                     annabanna
                        ^ ^
               *str='a'      
               --len=2        str[len]='a'
                 ++str
                 --len


                call palindrome(str, len);

                --->inside palindrome:

                         annabanna
                             ^
                   *str='b'      
                   --len=0        str[len]='b'
                     ++str
                     --len

                    call palindrome(str, len);
                    
                    --->inside palindrome:

                        len = 0  --> condition len <= 0 is true
                        return 1 --> success, found palindrome


NOTE:  if at any time, the *str character did not match
       the str[len] character, then the condition for 
       inequality would cause a return value of 0, 
       indicating failure, no palindrome found

[Griff0527]

jephthah I'm sure you are a good teacher, but I'm not getting this. I considered posting all 10 or 15 versions of the code I tried, but thought that would be excessive. I'm not sure if I am getting closer or further from the right answer at this point. Will you please take one more look for me? I appreciate it. This code was due this past Monday, but at this point, I'm not worried about the grade so much as I am the understanding of what I'm donig wrong.

#include <stdio.h>
 #include <string.h>
 #include <ctype.h>

 #define MAX_LEN 50

int
main(void)
{
/* Create variable for string */
char string[MAX_LEN];
int len;
/* Create external function */
char palindrome(char *string, int);

/* Explain purpose of program to user and prompts for input */
printf("This program will test a phrase inputted by you to see\n");
printf("if it is a palindrome.\n\n");
printf("Please enter a word or phrase of no more than 50 characters.\n\n>");


/* Receive input from user and stores it in input_string array */
scanf("%s", string);

/* Call external recursive function, receive the return value, and determine output */

if (palindrome(string, len)==1)
            printf("%s is a palindrome.\n",string);
        else
            printf("%s is not a palindrome.\n",string);
}

/* Recursive function to test first char to last char, second to second to last, etc. */


char palindrome (char *string, int len)
{
    len = strlen(string-1);

    if (len <=1)
        return 1;
    else if (string[0] != string[len])
        return 0;
    else return palindrome(++string, --len);

}

[jephthah]

ah, you're so close.

it's true you want to move the left hand "pointer" inward by one character each time. so you correctly do a "++string" as the first recursive argument in line 44.

it's also true that you want to move the right hand pointer inward by one place as well, so you do a "--len" as the second recursive argument.

but the *relative* position of the right hand "pointer" to the left hand pointer is actually decreased by *two* places each time. and since you're not actually using a real pointer there, but it's your "len" variable that determines the relative distance the right pointer is from the left, you need to decrement that length by a total of two.

you can do it a couple ways, by having "len = len - 2" as the second recursive argument, but you will then need to modify teh comparison value in line 40 to account for that. you could leave "--len" in line 44, and add a post-decrement to len in line 40 "len-- <= 1" or line a pre-decrement to len in line 42 "string".

any of those should do it.

(NOTE: if you hadn't been doing so already, you should have put some print statements after each conditional to see exactly what the left pointer is looking at, what the caluclated len value is, and what the right pointer is looking at each time.... it would really help your debugging to see what's going on)

[Griff0527]

FYI, on Tuesday, my instructor gave me this to work with... this was prior to any post I made here. I am providing this as a reference so you guys can see how far I went off track. I thought this might help you assist me more.

int palindrome(const char *string)
{
    int ans;
    char sub[MAX_LEN];

    if (strlen(string) <= 1) {
        ans = 1;
    } else if (string[0] != string[strlen(string)-1]) {
        ans = 0;
    } else {
       

         //so far it is a palindrom - the new string to check consists of the second letter and second to last letter - create it and check again

         ans = palindrome(sub);
    }   


    return (ans);
}

[Griff0527]

ok. I took your advice in your last post, and have been messing with it since. Would you mind compiling and running this? By the way, thank you for the reminder on the printf lines. I needed that reminder. I'm used the palindrome "anna" and my printf line gives an output of 4anna.

#include <stdio.h>
 #include <string.h>
 #include <ctype.h>

 #define MAX_LEN 50

int
main(void)
{
/* Create variable for string */
char string[MAX_LEN];
int len;
/* Create external function */
char palindrome(char *string, int);

/* Explain purpose of program to user and prompts for input */
printf("This program will test a phrase inputted by you to see\n");
printf("if it is a palindrome.\n\n");
printf("Please enter a word or phrase of no more than 50 characters.\n\n>");


/* Receive input from user and stores it in input_string array */
scanf("%s", string);

/* Call external recursive function, receive the return value, and determine output */

if (palindrome(string, len) == 1)
            printf("%s is a palindrome.\n",string);
        else
            printf("%s is not a palindrome.\n",string);
}

/* Recursive function to test first char to last char, second to second to last, etc. */


char palindrome (char *string, int len)
{
    len = strlen(string-1);

    if (len <= 1) {
        printf("%s %d", string, len);
       return 1;}
    else if (string[0] != string[--len]){
       printf("%s %d", string, len);
       return 0;}
    else return palindrome(++string, --len);


}

[jephthah]

the logic of your palindrome function was correct, but there were a few errors in your code structure that prevented the function from being executed properly.

. i have commented out the errors and put notes indicating what the error was.

#include <stdio.h>
 #include <string.h>
 #include <ctype.h>

 #define MAX_LEN 50

/* Create external function */
char palindrome (char *string, int len)
{
    //len = strlen(string-1);   <--- NO, do not try to take length of pointer!!
    //                               this is why "len" is passed in as an argument!
   
    
    printf("\nEntering palindrome():\n   str \"%s\", len %d\n", string, len);
 
    if (len <= 1) 
    {
       printf("   remaining length %d, all done \n", len);
       return 1;
    }
    else if (string[0] != string[--len])
    {
       printf("   str[0] \'%c\' != str[%d] \'%c\'\n", string[0], len, string[len]);
       return 0;
    }
    else 
    {
       printf("   str[0] \'%c\' == str[%d] \'%c\'\n", string[0], len, string[len]);
       return palindrome(++string, --len);
    }
}


int main(void)
{
/* Create variable for string */
    char string[MAX_LEN];
    int len;

    // char palindrome (char *string, int len);  <--- NO, do not declare prototypes 
    //                                                inside the main() function !!!


    /* Explain purpose of program to user and prompts for input */
    printf("This program will test a phrase inputted by you to see\n");
    printf("if it is a palindrome.\n\n");
    printf("Please enter a word or phrase of no more than 50 characters.\n\n>");


    /* Receive input from user and stores it in input_string array */
    scanf("%s", string);

    len = strlen(string);   // <-- DO get the length of the string after the input

    /* Call external recursive function, receive return value, determine output */

    if (palindrome(string, len) == 1)
        printf("\n%s is a palindrome.\n\n",string);
    else
        printf("\n%s is not a palindrome.\n\n",string);
}

[Griff0527]

I KNOW better than to declare prototypes inside the main function. I cannot believe that I overlooked that error. As for taking the length of len inside the function palindrome, I thought that looked wrong and didn't realize that I was taking the length of a pointer. I appreciate all of the help I received on this code. For my own sake, I will be practicing recursive functions to gain a better understanding of how they work. I'm starting to believe that online college is not the best way to learn programming, but I'm glad I was told about this site. You guys have been a great help.

[jephthah]

i figured it was a cut-and-paste typo .. they happen to everyone, don't sweat it too much. i almost didn't notice it, because its one of those that don't trigger a compiler warning. becoming able to see these improves w/ experience. just try to slow down.and not rush things when programming and debugging. sometimes you have to walk away and go do something different for a few hours and come back later. :)

also, i didn't note it, but changed your debug printfs... you were using %s when you needed to be using %c to print meaningful information.

good luck, and come back if you need more help :)