Week #5: Recursion

A recursive function is a function that calls itself. These functions are useful in programming as they provide an optimized method for implementing repetition in a program.

In Lab #3 we practiced tracing recursive functions involving nested lists. Here is an example given in the lab:

     def nd(L):
         ’’’(list or non-list) -> int
         ’’’
         if isinstance(L, list):

             return 1 + max([nd(x) for x in (L + [’ox’])])
         else: # L is a non-list

             return 0

This recursive function has an incomplete docstring. Therefore you have to carefully analyze the code given to figure what it does and you can test it with simple examples to confirm your understanding. When tracing a recursive function you must trace the function calls in order. You can replace return with --> and if you have already traced a similar call you can just plug in the result. For the example above we can trace nd('ox'), nd([2,3]), and nd([2, [3, 8], 5, [2, 6], 7]):

     (from lab #3 sheet)
     nd(’ox’)  
     --> 0 # ’ox’ is a non-list 

     nd([2,3])
     --> 1 + max([nd(x) for x in [2, 3, 'ox']])
     --> 1 + max([0, 0, 0]) #already traced nd of non-list
     --> 1 + 0
     --> 1

     nd([2, [3, 8], 5, [2, 6], 7])
     --> 1 + max([nd(x) for x in [2, [3, 8], 5, [2, 6], 7, 'ox']])
     --> 1 + max([0, 1, 0, 1, 0, 0]) #already traced nd of a non-list and a list consisting of non-lists
     --> 1 + 1
     --> 2