## can someone help me figure out this recursive algorithm?

Discuss all kind of algorithms and data structures from their mathematical and programming sides.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

### can someone help me figure out this recursive algorithm?

Recursive algorithm for an integer
If numDigiths <= 1 return true
Else check first and last digits num/10 numDigits-1 and num % 10
if they do not match return false
If they match, check more digits Apply algorithm recursively to: num % 10 numDigits-1 and numDigits - 2

what is the nuumdigits-1 after the 10.
david

### Re: can someone help me figure out this recursive algorithm?

david wrote:Else check first and last digits num/10 numDigits-1 and num % 10
[...]
what is the nuumdigits-1 after the 10.

It should be "num/(10^(numDigits-1))", where the ^ means "raised to a power", not "xor". That's just how to define what "the first digit" is. For example, take num=7652. numDigits=4. 10^(numDigits-1)=10^3=1000. num/1000 = 7652/1000 = 7 (if the division is truncating, as it normally is in C/C++).

Good luck.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

### would this be correct

would this be correct
Code: Select all
`bool palindrome(int z){   int firstdigit = 0;   int lastdigit = 0;   if (digitcounter(z) <= 1)   {      return true;   }   else   {      firstdigit = z /= (power(10,digitcounter(z) - 1));      lastdigit = z % 10;      if(firstdigit != lastdigit)      {         return false;      }      else      {         palindrome((z % power(10,digitcounter(z)-1) / (10 + digitcounter(z) -2)));       }   }}`
david

### Re: would this be correct

You don't need to put things in an `else' block if the body of the `if' ends in a `return'.

Where you said `/=' it should just be `/'.

The recursive call should be `return palindrome(...'.

You are calling `digitcounter' many times. Just call it once at the beginning and save the result in a local variable.

You don't need to initialize local variables to values that are never used. Also, you can delay the declaration until the place where they are used.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA