Python Modules; Introduction to Recursion

  Python moduleIf you quit the Python interpreter and enter it again without saving your program to a text file, the definitions you have made will be lost. Therefore, if you want to write a somewhat longer program, you are better off using a text editor to prepare the input for the interpreter and running it with that file as input instead. In doing so, we create scripts. As your program gets longer, you may also want to split it into several files for easier maintenance.

Python Modules

To support this, Python provides a way of putting definitions into a file and using them in a script or in an interactive instance of the interpreter. Such a file is called a module; definitions from a Python module can be imported into other modules or into the main Python modules.

A Python module is a file containing Python definitions and statements; such a file always ends with the suffix .py. Up to this point, we have not introduced Python definitions. A definition in Python always starts with def and is followed by its name. This is the equivalent of a function in C or Pascal. For example:

def hello():
        print(‘Hello, world!’)

is a very simple Python function to print out “Hello, world!”. If this code is saved in a file called hello.py, and is in Python’s path, you can import it at the Python command line:

>>> import hello

Once the Python module is imported, you can invoke the hello function with:

>>> hello.hello()

As with C and other languages, you can specify parameters. For example:

def isZero(a):
    if a == 0:
       print('a is zero')
    else:
       print('a is a non-zero number')

You can also return a value from the function:

def isZero(a):
     if a == 0:
        return True
     else:
        return False

As in other languages such as C/C++, we can specify default parameters. For example:

def isZero(a=0):

allows us to invoke the function isZero with no arguments; the interpreter will insert a value of 0 for a if no arguments are specified. However, a non-default argument cannot follow a default argument. Thus:

def isZero(a=0,b):

is not allowed, but:

def isZero(a,b=0):

is allowed.

This is a decent start, but it would be nice if we came up with a program that can do something useful.

Introduction to Recursion

In computer science, recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem. Recursion always involves the existence of one more more base cases in which an operation can be done directly on the input data. The other cases involve invoking the same function on a subset of the input data in a divide-and-conquer strategy. The approach can be applied to many types of problems – for example, finding palindromes. It shouldn’t be too difficult to come up with a Python module to solve this problem.

A palindrome is a word, phrase, number, or other sequence of symbols or elements that read the same forward or reversed: for example, “Race car”, or “A man, a plan, a canal – Panama”. A solution of the problem for finding a palindrome using recursion can be outlined as follows:

  1. If the input string length is 0 or 1, then we have a palindrome – return true
  2. If the input string length is greater than 1 but the first and last character match, apply the test recursively to the string minus the first and last characters
  3. If [1] and [2] don’t apply, then we don’t have a palindrome – return false

Successive applications of this process on the input string will eventually yield either a mismatch between the first and last character or an input string of length 0 or 1, and the test will be complete. We can code this algorithm in Python as follows:

def isPalindrome(myString):
  ''' Simple program to find palindromes, part of our Python module
  Parameters: myString => string to perform test on
  If length <= 1, it's a palindrome - return True
  If first char is the same as the last char, apply algorithm recursively
  Otherwise return False '''
  if len(myString) <= 1:
     return True
   elif myString[0].lower() == myString[len(myString)-1].lower():
     return isPalindrome(myString[1:(len(myString)-1)])
  return False
 

Our isPalindrome function takes in a single argument, myString. We introduced two hitherto unseen functions here. len() takes a single parameter – a string – and returns the length. lower() is a member of the string class and converts the string into lowercase. This ensures that our test is not case-sensitive. You may have noticed that there is one shortcoming of this algorithm: if there are spaces or any other alphanumeric content in the string, it will return false. I decided it would be easier to write a separate function to strip the non-alphanumeric characters out:

 def convertToAlphaNum(myString):
  ''' Iterate through the string and generate an output string with only the alphanumeric chars (also part of the palindrome.py Python module)
  Parameters: myString => the string to convert
  Returns: A copy of the string with all non-alphanumeric
  characters removed '''
  retval = ''
  for c in myString:
      if c.isalpha() or c.isdigit():
          retval += c
  return retval

All this function does is iterate through the input string and if a character is a letter or digit, it gets added to a new string. When it is done, the function returns the new string. We still need a function to read input from the user and call these functions, so that will be our next bit of code, and the last function in our Python module:

def testPalindrome():
 ''' Part of the palindrome. py Python module - Prompt user for string input
 Output whether it is a palindrome or not '''
 myString = str(input('Enter a string: '))
 if isPalindrome(convertToAlphaNum(myString)):
    print(myString,'is a palindrome')
 else:
    print(myString,'is not a palindrome')

This function simply prompts the user to input a string and uses the previous functions to determine whether or not it is a palindrome, and prints the results.

Once these functions are saved to a file, you can load the file into IDLE using the File -> Open menu option (or CTRL-O). The Python module will load into a separate window; from that window, select Run -> Run Module (or press F5). Then from the main IDLE window, you can run testPalindrome():

>>> testPalindrome()
Enter a string: sample text
sample text is not a palindrome
>>> testPalindrome()
Enter a string: A man, a plan, a canal – Panama
A man, a plan, a canal – Panama is a palindrome
>>> testPalindrome()
Enter a string: No ‘x’ in Nixon
No ‘x’ in Nixon is a palindrome
>>> testPalindrome()
Enter a string: No ‘x’ in Ford
No ‘x’ in Ford is not a palindrome
>>> testPalindrome()
Enter a string: Able I was, ere saw I Elba
Able I was, ere saw I Elba is a palindrome

The source code for for these functions is available as a single Python module, via this link.

It’s not the most elegant solution, but it does seem to work. In the next article, we will continue our look at programming in Python, including a second look at using recursion to solve problems.

External Links:

Python documentation from the official Python website