# Recursive function problem

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

• Try following the code through with a pencil and paper. What do you get? – David Richerby Sep 27 '15 at 15:14
• I get the same thing, 5310. When f(0) is called the algorithm prints n%10 which is 0 and then: if(0!=0)? No. Isn't the second print ignored? – Sim Sep 27 '15 at 15:25
• Try tracing it on pencil and paper and edit the question to show each step: show each recursive call to f, and what is printed at each step, in what order. – D.W. Sep 27 '15 at 19:27

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.

• isn't the second print ignored after the if statement? – Sim Sep 27 '15 at 15:35
• No, why would it be? The code is executed in the way you write it. – Yuval Filmus Sep 27 '15 at 15:37
• well because if test whether n is different from 0 or not. – Sim Sep 27 '15 at 16:39
• Try running the code in a debugger to see what really happens. After a recursive call to $f$, execution returns to the parent instance of $f$, and at that point the second print is executed. – Yuval Filmus Sep 27 '15 at 16:47
• I think I get it now:) (correct me if I am wrong). After the if statement the function passes through the stack levels again in an opposite direction. – Sim Sep 27 '15 at 17:38

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.

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.

• Don't forget the second print, upon return from the recursive call. – Yves Daoust Sep 27 '15 at 20:14