MITx and the Python DUDE .: I completed all the video tutorials and practice exercises assigned this week. Left unfinished is the Week 2 Problem Set (due Feb 2nd).
The big idea this week is recursion and creating functions in Python that call themselves to solve problems. One of the exercises involved finding the greatest common divisor of two positive integers (that is, the largest integer that divides each of them without remainder). Here is a cool animated example of recursion using Euclid's algorithm to find the GCD of two numbers.
Translated into Python code ...
def gcdRecur(a, b): ''' a, b: positive integers returns: a positive integer, the greatest common divisor of a & b A clever mathematical trick (due to Euclid) makes it easy to find greatest common divisors. Suppose that a and b are two positive integers: If b = 0, then the answer is a Otherwise, gcd(a, b) is the same as gcd(b, a % b) ''' if b == 0: return a else: return gcdRecur(b, a % b)
A big help trying to figure out how to code solutions this week was the online Python Tutor resource. It allows you to insert your code and then visualize what the computer is doing step-by-step as it executes the instructions. Here is an exercise which required writing a recursive function that executes a bisection search to determine if a character is in a string (the MITx grader uses example strings that are sorted in alphabetical order) ...
set tabstop=4 " number of columns occupied by a tab character set softtabstop=4 " see multiple spaces as tabstops so <BS> does the right thing set expandtab " converts tabs to white space set shiftwidth=4 " width for autoindents set autoindent " indent a new line the same amount as the line just typed set number " add line numbers set cc=80 " set an 80 column border for good coding style