Going Back

Reversing the digits of a number is a time-honoured exercise for student programmers. It gets the student to think about integer division and modulo operations, and about iterative processes.

An exercise I've often give to my students is to write a recursive procedure for reversing an integer's digits, even though I know that it can be done more simply as a loop. This is a good way to have the students think about parameter passing and variable scope. But up till now, I've only had students doing this in Pascal.

So when I went to do it in Python, I found myself momentarily stopped by the fact that Python does not have an exact equivalent to Pascal's variable parameters. So how do I get a recursive procedure for integer reversal in Python?

I came up with two solutions.

Solution 1:

revers(n):
global q #tell Python to use the global variable, not a local one
if n > 0:
  q=q*10+n%10
  revers(n/10)
return q

q = 0
x=int(raw_input("Enter a number: "))
print revers(x)

Here, I simply made the function calculate the reversed integer in a global variable. Now, when I was learning Pascal programming, all my reference works said the same thing: don't change a global variable inside a function/procedure. Since old habits die hard, I found myself looking for a different solution to the one above, one that didn't require the global variable inside the function.

Solution 2:

revers(n,q=[0]):
if n > 0:
   q[0]=q[0]*10+n%10
   revers(n/10)
return q[0]

x=int(raw_input("Enter a number: "))
print revers(x)

This solution uses the fact that arguments to Python functions are object references, so passing a mutable object (a list being an obvious example) allows you to progressively alter the value in that object with each subsequent recursive call to the function.

Python also allows you to declare a default value for an argument and thereby omit it from the function call. The default value is evaluated only once, so setting using q=[0] as an argument only affects the first call to the function, and subsequent recursive calls do not reset the list.

As a solution, I prefer this (since it doesn't violate the rules about variable scope I learned so long ago), but I wonder how well my students will understand how the mutability of an object relates to the scope of a recursive function.

Getting Keith Backwards

I stumbled over an interesting number sequence the other day - Keith numbers (named for mathematician Mike Keith) are found as follows: starting with a number, separate the digits, then add them to form another number; continuing to sum the last n numbers in the sequence (where n is the number of digits in the original number), if the original number appears in the sequence, it is a Keith number.

For example, starting with 14, we get 1+4 = 5, 4+5=9, etc. to form the sequence 1, 4, 5, 9, 14 - since the original (14) appears in the sequence, 14 is a Keith number.

It turns out that Keith numbers are very rare (Wikipedia's article states that there are only 71 Keith numbers below 10¹⁹).

I wondered about similar number sequences, in particular numbers that produce the original number with its digits reversed. Wolfram's MathWorld site has an article on Keith numbers that also mentions these Reversed Keith numbers, but prefers the ugly term revrepfigits (and also calls Keith numbers repfigits, from 'repetitive fibonnaci-like digits').

Before I read the Wolfram MathWorld article, I had written a small Python program to find Reverse-Keith numbers (which I had decided should be called Feek numbers), and generated all the numbers up to 10 000 000.

This turns out to be a nice little programming exercise, requiring one to think about how to manage both integer reversal and splitting an integer into its separate digits prior to building the resulting number sequence. If someone wants an interesting exercise for their students, I think this is worth a look.