By
Vasudev Ram
Image: Squares. Attribution: Vasudev Ram.I got this idea to compute some simple functions using recursion, after browsing a chain of links recently, that happened to lead me to the original paper about
Lisp,
RECURSIVE FUNCTIONS OF SYMBOLIC EXPRESSIONS AND THEIR COMPUTATION BY MACHINE (Part I), by its inventor,
John McCarthy. I remembered that I had come across it, maybe in a public library, in my college days, and had read it then.
Anyway, I didn't understand the whole paper at the time, but did understand some of the examples of recursion. So today I thought of implementing, just for fun, a few simple algorithms in a recursive way, even though there exist simple non-recursive solutions for them.
So here are a few simple recursive algorithms:
1: Recursive computation of list length:
This uses recursion to find the length of a Python list, i.e. it does what the built-in function len() does. Languages that support recursion often use the terms head and tail of a list, to mean the first item of the list, and the rest of the list (not counting the first item). Of course, the tail of a list is also a list, which is where the recursive algorithm comes in. So the length of a list can be defined recursively as:
0, if the list is empty (i.e. contains no items)
or
1 + the length of the tail of the list, if the list is non-empty, i.e. if it has at least one item in it.
This is a recursive definition because we are using the concept of the list's length in the very definition of its length. As long as the recursive calls terminate at some point, the definition will work.
The code for rec_list_len.py:
# Recursive list length computation.
def rec_list_len(lis):
if not lis:
return 0
#print "calling rec_list_len with lis = {}".format(lis)
return 1 + rec_list_len(lis[1:])
print "Recursive computation of list length:"
print
for lis_siz in range(5):
lis = range(lis_siz)
lis_len = rec_list_len(lis)
print 'List: {} Length: {}'.format(lis, lis_len)
print
# Also test rec_list_len on other kinds of sequences than lists:
s = 'hello there'
print 'String: "{}" Length: {}'.format(s, rec_list_len(s))
print
s = 'the quick brown fox'
print 'String: "{}" Length: {}'.format(s, rec_list_len(s))
print
student = ('Jack', 25, 'New York')
print 'Tuple: {} Length: {}'.format(student, rec_list_len(student))
print
student = ('Jill', 27, 'Paris', 'France')
print 'Tuple: {} Length: {}'.format(student, rec_list_len(student))
print
Running the program gives this output:
$ python rec_list_len.py
Recursive computation of list length:
List: [] Length: 0
List: [0] Length: 1
List: [0, 1] Length: 2
List: [0, 1, 2] Length: 3
List: [0, 1, 2, 3] Length: 4
String: "hello there" Length: 11
String: "the quick brown fox" Length: 19
Tuple: ('Jack', 25, 'New York') Length: 3
Tuple: ('Jill', 27, 'Paris', 'France') Length: 4
Notice that in the above output, we also have the length of strings and tuples computed by the same function. This works, even though I initially wrote the function only to compute list lengths, because lists, strings and tuples are all kinds of Python sequences, and the code I've used in the function is valid for any Python sequence that supports slicing. Lists, strings and tuples all do.
Also, if you uncomment the print statement in function rec_list_len, and run the program, you will see that successively smaller segments (tails, really) of the list are being passed to the function on each (recursive) call. This will help understand what is going on, if it seems unclear otherwise.
This program demonstrates, via a simple computation, the essence of the recursive approach to problem-solving: defining the solution in terms of smaller problems of the same kind. But
recursion can also be used to solve harder problems, often
elegantly and with a relatively simple algorithm, once we have figured out to solve the original problem in terms of sub-problems of the same kind. For example,
tree traversal.
[ It's also worth noting that any recursive solution can be transformed (manually, by the programmer) into an iterative solution that does not use recursion, and uses a while or for loop and a stack instead, and this is sometimes done for the sake of efficiency. ]
Once we've worked out the logic for recursive length computation, code for similar computations on a list is straightforward, with only minor changes from the above:
2: Recursive computation of sum of numbers in a list:
This uses recursion to find the sum of the numbers in a Python list, i.e. it does what the built-in function sum() does.
The code for rec_list_sum.py:
# Recursive list sum computation.
# Assumes list items are numbers.
def rec_list_sum(lis):
if not lis:
return 0
return lis[0] + rec_list_sum(lis[1:])
for r in range(5):
lis = range(r)
print "Sum:", rec_list_sum(lis), "List:", lis
Program run and output:
Sum: 0 List: []
Sum: 0 List: [0]
Sum: 1 List: [0, 1]
Sum: 3 List: [0, 1, 2]
Sum: 6 List: [0, 1, 2, 3]
3: Recursive computation of product of numbers in a list:
This uses recursion to find the product of the numbers in a Python list.
The code for rec_list_product.py:
# Recursive list product computation.
# Assumes list items are numbers.
def rec_list_product(lis):
if not lis:
return 1
return lis[0] * rec_list_product(lis[1:])
for r in range(1, 7):
lis = range(1, r)
print "Product:", rec_list_product(lis), "List:", lis
Program run and output:
$ python rec_list_product.py
Product: 1 List: []
Product: 1 List: [1]
Product: 2 List: [1, 2]
Product: 6 List: [1, 2, 3]
Product: 24 List: [1, 2, 3, 4]
Product: 120 List: [1, 2, 3, 4, 5]
And that images of nested squares at the top of the post? You guessed it, it's generated by a
Python turtle graphics program - not the preceding link in this sentence, that's for the graphics module; see below for the program.
It's a
recursive program, naturally :)
Here is the code for the squares program, pasted straight from an
IPython session, where I wrote and ran it:
In [63]: def square_and_move(side, dist):
....: square(side)
....: t.penup()
....: t.forward(dist)
....: t.right(90)
....: t.forward(dist)
....: t.left(90)
....: t.pendown()
....: side -= 20
....: if side >= 60:
....: square_and_move(side, dist)
....:
In [64]: square_and_move(200, 20)
in which, function
square has the obvious definition of drawing a square of the given size (the argument 'side'), by moving
forward(side) and then doing
right(90), four times each.
Here is the basis of another turtle graphics program that let's you
draw stuff interactively.
-Enjoy.
-
Vasudev Ram - Online Python training and programming Signup to hear about new products and services I create. Posts about Python Posts about xtopdf My ActiveState recipes
