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.
f
, and what is printed at each step, in what order. $\endgroup$