Welcome, guest | Sign In | My Account | Store | Cart

This recipe shows how to compute some simple list functions (functions that operate on lists) using simple recursive algorithms. Simple non-recursive algorithms exist for these tasks; this recipe is just for illustrative purposes. However, the principles described can be used for more complex recursive algorithms, for which non-recursive algorithms might be more complex than the recursive ones.

Python, 63 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63``` ```#--------------------------------------------------------------------- # Recursice computation of list length: 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 #--------------------------------------------------------------------- # 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 #--------------------------------------------------------------------- # 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 #--------------------------------------------------------------------- ```

More discussion and sample output at this link:

Recursive computation of simple functions:

 Created by Vasudev Ram on Tue, 1 Mar 2016 (MIT)

### Required Modules

• (none specified)