Cheap and Secure Web Hosting Provider : See Now

[Answers] Recursive function problem

, , No Comments
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;     } } 
Asked By : Sim

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47611

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback