Cheap and Secure Web Hosting Provider : See Now

, ,
Problem Detail:

This might seem very simple but it's been giving me lots of headaches.

For example if I run f(12345) the result is 5310135.

I understand why it would return 5310, the rest of 135 is what is giving me troubles. Sorry if the question sounds dumb, I am a newbie seeking for help:).

``function f (integer n) {     print n%10;     if (n!=0)     {         f(n/100);         print n%10;     } } ``

#### Answered By : Yuval Filmus

You missed the second print instruction.

We can rephrase the algorithm as follows:

``function f (integer n) {   if n equals 0 {     print 0   } else {     print n % 10     f(n/100)     print n % 10   } ``

Now we can do "recursion unrolling":

``function f (integer n) {   if n equals 0 {     print 0   } else {     print n % 10     if n/100 equals 0 {       print 0     } else {       print (n/100) % 10       f(n/10000)       print (n/100) % 10     }     print n % 10   } ``

One more level:

``function f (integer n) {   if n equals 0 {     print 0   } else {     print n % 10     if n/100 equals 0 {       print 0     } else {       print (n/100) % 10       if n/10000 equals 0 {         print 0       } else {         print (n/10000) % 10         f(n/1000000)         print (n/10000) % 10       }       print (n/100) % 10     }     print n % 10   } ``

Suppose for the moment that all of `n`, `n/100`, `n/10000` differ from zero. The executed code is then

``print n % 10 print (n/100) % 10 print (n/10000) % 10 f(n/1000000) print (n/10000) % 10 print (n/100) % 10 print n % 10 ``

Hopefully you can see the pattern.

The printed string is always an odd-length palindrome with a `0` in the middle, a property which you can prove by induction.