Week #7 - Recursion

For my Week #7 blog post please refer to my post about Recursion from Week #5.

Week #6: Object-Oriented Programming (OOP)

What is Object-Oriented Programming?

Object-Oriented Programming is type of programming that consists of objects that are manipulated to satisfy the needs of the program.

Object-Oriented Programming is what this course has been mainly focusing on. So far we have learned about how to create classes and methods including special methods such as __init__, __repr__, __str__, __eq__. To create an object you create an instance of a class.

We also learned about an important OOP concept called inheritance. Inheritance is when a class inherits code or behaviour from another class. The class inheriting the code is called the subclass or child class and the other is called the parent class.  Inheritance was a large component of Assignment 1. In the assignment we created two main parent classes for a general game state and a general strategy. These parent classes had subclasses of a state of a specific game called Subtract Square and a specific strategy that chooses randomly what move the computer makes.

Overall these are some of the concepts of Object-Oriented Programming that we have covered so far, and I'm looking forward to what we learn next!

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