I have to check a number is palindrome or not by recursion

Question

int main()
{
  int i,n;     
  printf("Enter the number");
  scanf("%d",&n);     
  i=pali(n);    
  if(n==i) 
    printf("Number is pall"); 
  else     
    printf("Not Pall");  
}  

int pali(int n) 
{   
  int r;  
  static sum=0;  
  if(n!=0) 
  {      
    r=n%10;    
    sum=sum*10+r;   
    pali(n/10);  
  }  
  return sum;
}

I used a static variable to add up the sum. Is there any way where no static variable will be used?

Answer 1

You can make a function that check only the first and the last digits of the number and pass the rest of the number onward.

To explain better, think about the following cases:

• pali(1220) would check for the first (1) and last (0) digits. Since 1 != 0 pali would return false.

• pali(17891) would check first (1) and last (1). Since they're equal then the function would recursively return pali(789) (which itself would return false since 7 != 9).

• pali(878) would check that 8=8 and recursively return pali(7)

• pali(3) would check that first (3) and last (3) numbers are equal and return 0.

The challenge here is to develop an algorithm that:

• Check if first and last numbers are the same (even if it's only one digit!)

• Strip the number from first and last digits and call itself on the remainder

Then all you need to do is apply recursion. Here's a sample implementation:

int pali(int number)
{
    int smallDigit, bigDigit;

    /* When recursion ends suceffuly*/
    if (number == 0)
        return 1;

    /* Check for first and last digit of a number */
    smallDigit = number % 10;
    bigDigit = number;

    while(bigDigit/10!=0)
    {
        bigDigit = bigDigit/10;
        smallDigit = smallDigit*10;
    }

    /* Check to see if both digits are equal (Note: you can't use smallDigit here because it's been multiplied by 10 a few times) */
    if (bigDigit != number%10)
        return 0;
    else
    {
        number = (number - smallDigit)/10; /* This is why smallDigit was multiplied by 10 a few times */
        return pali(number); /* Recursion time */
    }
}

Answer 2

Sure, you can do it this way :

#include <stdio.h>

int pali(int n)
{
  int sum = 0;
  int keeper = 0;
  for (int i = n; i > 0; i /= 10) {
    if (keeper != 0) {
      sum *= 10;
      sum += (keeper - i * 10);
    }
    keeper = i;
  }
  sum *= 10;
  sum += keeper;
  return sum;
}

int main(int argc, char** argv)
{
  int i, n;     
  printf("Enter the number : ");
  scanf("%d",&n);
  i = pali(n);
  if(n == i) 
    printf("Number is palindrome"); 
  else     
    printf("Not Palindrome");  
}

Using recursion is even easier :

#include <stdio.h>

int pali(int n, int sum)
{
  sum += n - ((n / 10) * 10);
  n /= 10;
  if (n > 0)
    pali(n, sum * 10);
  else
    return sum;
}

int main(int argc, char** argv)
{
  int i, n;     
  printf("Enter the number : ");
  scanf("%d",&n);
  i = pali(n, 0);
  if(n == i) 
    printf("Number is palindrome"); 
  else     
    printf("Not Palindrome");  
}

And a recursive version with only one parameter :

#include <stdio.h>

int pali(int n)
{
  int fUnit, lUnit;
  fUnit = n;
  int mul = 1;
  while (fUnit > 10) {
    fUnit /= 10;
    mul *= 10;
  }

  lUnit = n - ((n / 10) * 10);
  n -= (fUnit * mul);
  n /= 10;

  if (mul == 1) return 1;
  else if (fUnit == lUnit) return pali(n);
  else return 0;
}

int main(int argc, char** argv)
{
  int n;     
  printf("Enter the number : ");
  scanf("%d",&n);
  if(pali(n) == 1) 
    printf("Number is palindrome"); 
  else     
    printf("Not Palindrome");  
}

Answer 3

Here is an optimized version that

• Doesn't use local static.
• Only includes stdio.h
• Uses recursion.

---

#include <stdio.h>

static void perform_useless_recursion (int n)
{
  if(n--)
  {
    perform_useless_recursion(n);
  }
}

_Bool is_pali (int n)
{
  perform_useless_recursion(1);

  int sum = 0;
  for(int i=n; i!=0; i/=10)
  {
    sum = sum*10 + i%10;
  }
  return n == sum;
}

int main (void)
{
  int n=5005;

  if(is_pali(n)) 
    printf("Number is pall"); 
  else     
    printf("Not Pall");  

  return 0;  
}

The code could be improved even further by removing the perform_useless_recursion() function.

The advantage of this code is that the actual calculation is performed by a fast loop, instead of slow, dangerous recursion. In the real world outside artificial school assignments, there is no reason to write inefficient and dangerous code when you could write efficient and safe code. As a bonus, removing recursion also gives far more readable code.

If you benchmark this code you'll notice that it will be faster than all other versions posted and consumes less memory.

Answer 4

Since your function returns sum you could replace this line:

pali(n/10);

with

sum=pali(n/10);

You'd also have to move it up a line too.

Answer 5

Yes, the typical ("functional") approach is to carry the state in the form of a function argument. This often makes it necessary/nice to have a second function that does the actual recursion, which you can start by calling with the proper initial values for the state:

int do_pali(int sum, int n)
{
  if(n != 0)
  {
    const int r = n % 10;
    return do_pali(10 * sum + r, n / 10);
  }
  return sum;
}

the public function then just becomes:

int pali(int n)
{
  return do_pali(0, n);
}

In languages with inner functions this can be more neatly expressed (GCC supports this as an extension).