Recursive function problem

Question

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;
    }
}

Answer 1

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.

Answer 2

Don't think in terms of "stack levels" or such for recursive functions. Say you have:

f(n)
{
   /* do something */
   g(n - 1);
   /* more stuff */
}

if you call f(n) you expect something done, then g(n - 1) is completely worked through, and finally comes more stuff. If f and g happen to be different or the same function is irrelevant, it is done the exact same way. And the only sane way to understand recursive functions is as above: When hitting a recursive call, just assume (for now) that f does it's work correctly in the recursive call, and that under that condition the body of the function does it's job correctly. You have to reason separately that there are conditions under which there are no further recursive calls (and the results in those cases are right), and that recursive calls get you somehow "closer" to those base cases. Exactly the same way you reason if f and g are different, you analyse the called function separately.

Answer 3

The following gets executed:

f(12345)
│   print 12345 % 10
│   f(123)
│   │   print 123 % 10
│   │   f(1)
│   │   │   print 1 % 10
│   │   │   f(0)
│   │   │   └   print 0 % 10
│   │   └   print 1 % 10
│   └   print 123 % 10
└   print 12345 % 10

The function prints every other digit (units included) in reverse order, then 0, then these digits in direct order: 12345 -> 1 3 5 -> 531 0 135.