Solved

palindrome with recursion

Posted on 2004-10-27
584 Views
Last Modified: 2010-04-01
I am trying to write a palindrome function  that will tell me if a number is a palindrome. The tricky part about this, I think, is that I want to call the following two recursive functions from within the palindrome() to do the work.

-----------------------
unsigned digitCounter(int number)
{    
     if (number != 0)
       {
             return digitCounter(number / 10) + 1;
       }
     else
       {
             return 0;
       }
}
---------------------
int power(int x, unsigned n)
{
      if (n == 0)
      {
            //anchor case
            return 1;
      }
      else
      {      //inductive case (n > 0)
            return x * power(x, n - 1);
      }
}
---------------------
Here is what I have for the palindrome() so far, but its not quite right.

bool palindrome(int number)
{
      int firstDigit, lastDigit;
      if (number == 1)
      {
            return true;
      }
      else

            firstDigit = number / (10 ^ numDigits - 1);
            //gives last digit
            lastDigit = number % 10;
            
            if (firstDigit != lastDigit)
            {
                  return false;
            }
            else
            {
                  palindrome(number % 10) / 10 && lastDigit - 2;
            }
}
0
Question by:jandhb
    6 Comments
     
    LVL 9

    Expert Comment

    by:jhshukla
    bool palindrome(int number)
    {
         int firstDigit, lastDigit;
         /* calculate numDigits here. the function looks correct */

         if (numDigits == 1)
         {
              return true;
         }
         else

              firstDigit = number / (10 ^ numDigits - 1);
              lastDigit = number % 10;
             
              if (firstDigit != lastDigit)
              {
                   return false;
              }
              else
              {
                   int newNumber = number - firstDigit*(10 ^ numDigits - 1); //remove first digit
                   newNumber /= 10; //remove last digit
                   palindrome(newNumber);
              }
    }
    0
     
    LVL 39

    Expert Comment

    by:itsmeandnobodyelse
    >> I want to call the following two recursive functions from within the palindrome()

    But you didn't...

    bool palindrome(int number)
    {
         int firstDigit, lastDigit;
         
         int numDigits = digitCounter(number);

         if (numDigits == 1)
         {
              return true;
         }
         else
         {
              int dec = 10;
              for (int i = 0; i < numDigits-1; ++i)
                   dec *= 10;
              firstDigit = number / dec;
              lastDigit = number % 10;
             
              if (firstDigit != lastDigit)
              {
                   return false;
              }
              else
              {
                   int newNumber = number - dec; //remove first digit
                   newNumber /= 10; //remove last digit
                   return palindrome(newNumber);
              }
         }
    }

    Regards, Alex
    0
     
    LVL 12

    Expert Comment

    by:stefan73
    Hi jandhb,
    Do you need to process your number as an integer? It's a lot easier when you convert it into text first:

    bool palindrome(int number){
        char ptext[12]; /* 10 digits, sign and trailing \0 */

        sprintf(ptext,"%d",number);

        return is_palindrome(ptext,0,strlen(ptext)-1);
    }

    ...I'm sure you can easily write the is_palindrome() function yourself.


    Cheers!

    Stefan
    0
     
    LVL 1

    Author Comment

    by:jandhb
    Do you need to process your number as an integer?

    The number I will be passing to this function will be an integer. In your examples where are you calling the two other functions from within the palindrome()? These recursive functions need to be called to do the work. Maybe I'm missing it. Here again are the two other functions....

    unsigned digitCounter(int number)
    {    
         if (number != 0)
           {
                 return digitCounter(number / 10) + 1;
           }
         else
           {
                 return 0;
           }
    }
    ----------------------------------------------
    int power(int x, unsigned n)
    {
          if (n == 0)
          {
                //anchor case
                return 1;
          }
          else
          {      //inductive case (n > 0)
                return x * power(x, n - 1);
          }
    }
    ----------------------------------------

    0
     
    LVL 39

    Accepted Solution

    by:
    >>>> Maybe I'm missing it.

    Yes, i used digitCounter in the post above. I didn't use power(), but made a while loop calculating the power of 10 myself. I removed some errors and used both  functions now:

    unsigned digitCounter(int number)
    {    
         if (number != 0)
          {
               return digitCounter(number / 10) + 1;
          }
         else
          {
               return 0;
          }
    }

    int power(int x, unsigned n)
    {
         if (n == 0)
         {
              //anchor case
              return 1;
         }
         else
         {     //inductive case (n > 0)
              return x * power(x, n - 1);
         }
    }


    bool palindrome(int number)
    {
         int firstDigit, lastDigit;
         
         int numDigits = digitCounter(number);

         if (numDigits <= 1)
         {
              return true;
         }
         else
         {
              int dec = power(10, numDigits-1);
              firstDigit = number / dec;
              lastDigit = number % 10;
             
              if (firstDigit != lastDigit)
              {
                   return false;
              }
              else
              {
                   int newNumber = number - (firstDigit*dec); //remove first digit
                   newNumber /= 10; //remove last digit
                   return palindrome(newNumber);
              }
         }
    }

    Regards, Alex
    0
     
    LVL 1

    Author Comment

    by:jandhb
    Alex, thank you very much for your help here.
    0

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Live - One-on-One C++ Help from Top Experts

    Solve your toughest problems, fast.
    C++ experts are online now and ready to help you.

    Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
    Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
    The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
    The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

    846 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    8 Experts available now in Live!

    Get 1:1 Help Now