Web Developer

MIT Python Programming #4

Decomposition and abstraction through functions; introduction to recursion

Massachusetts Institute of Technology: Introduction to Computer Science and Programming

Lecture 4: Decomposition and abstraction through functions; introduction to recursion

Instructors: Prof. Eric Grimson, Prof. John Guttag

View the complete course at: http://ocw.mit.edu/6-00F08

Introduction to Computer Science & Programming Class Notes

In the previous 3 lessons we learned the following in our language:
– Assignment
– Conditionals
– Input/Output
– Looping Constructs (For, While)

Touring Complete: The above fundamentals are enough to write
any program. (This is technically correct, but to use just these would make writing
a program difficult.)

Decomposition & Abstraction

Decomposition – A way to give the code structure. Its a way
to break code into modules. Modules that make sense on their own, modules that can
be reused in many places. Modules that isolate components of the process.

Abstraction – Allows the ability to suppress the details, bury
away specifics of something, and treat composition like a "black box". Literally
behaves like a mysterious black box. Constructs within black box take input and
give output while suppressing the definition as to how the results are achieved.

Abstraction and decomposition allows us to "abstract" code separately. Separates
from other modules of code.

One mechanism for abstraction is functions.

– break up into modules
– suppress details
– create a new "primitive"

The idea of a function is that you capture a common pattern of computation.
Example: A block of code computes a square root. We can capture this block, give
it a name. Details of how square root is computed is surpressed.

This in turn can create a new primitive. Addition and subtraction are examples
of mathematical primitives.

What do you need to build abstractions, and how do you make it so they work together?
Analogy: You were hired by PBS to write a 13 hour drama. You decide
to break it up into 13 different sets and hire a writer to write a one hour portion.
Each hour of drama is written great but has absolutely nothing to do with the other
dramas. For this to work correctly you would need a contract with specifications.
You would tell each writer that here is what you need at the input
of the drama, and here is what I need at the output of
the drama. The details of what happens inside the hour are up to them.

This analogy is exactly what needs to be done within our functions.

Creation of a Function in Python:
Line 1: def sqrt(x):
##Returns the square root of x, if x is a perfect square.
##Prints an error message and returns None otherwise
Line 2: ans = 0
Line 3: if x >= 0:
Line 4: while ans*ans < x: ans = ans + 1
Line 5: if ans*ans != x:
Line 6: print x, 'is not a perfect square'
Line 7: return None
Line 8: else: return ans
Line 9: else:
Line 10: print x, 'is a negative number'
Line 11: return None

Line 13: def f(x):
Line 14: x = x + 1
Line 15: return x

Line 1: def sqrt(x) Keyword def. (Creates a
function) Followed by a name(sqrt stands for square root). sqrt (x)
The x defines the formal parameters. In other words if x is given a value
that value within the body of this function, that value will be used anywhere x
is used.
Line 7, 8, 11, 15: Keyword return. Return states that when you
get to this point in the computation. Stop the computation. Return the control from
this function and take the value of the next expression (none, return ans,
return x
) and return that as the value of the whole computation.

None: Has a special value. None states that their is no value
coming back from this computation. When this returns to the interpreter it doesn't

Every path ends in a return in this particular code. This is a good program discipline.

Invoke a function by passing in values for the parameters.
Input 16: sqrt(16) This binds the value of x to
16. This binding is local. Only holds to this procedure.

Local bindings do not affect any global bindings.

When you type things in Python, (Example: type x = 3) you are getting what's
called global bindings.

Call function: Think of it as creating a local table within the interpreter.
The value of x = 16 is only bound to the table sqrt. When a return is stepped into,
a value is given back to the interpreter and the sqrt table goes away

Local Binding

Decomposition? Suppose I wanted to use the square root construct in hundreds
of places in my program. Without a function it would have to be copied everywhere.
Now their is just one simple thing, as we have simply isolated the sqrt function
within that module.

Abstraction? We have part of what we want with abstraction. Abstraction is a
suppression of details.

Lets use what we have learned to solve a problem.

Farmyard Problem
A farmer has a bunch of pigs and a bunch of chickens.
He walks out into the farmyard and observes 20 heads and 56 legs.
How many pigs and how many chickens does he have?
numP + numC = 20
4* numP + 2* numC = 56

To solve the farmyard problem we will enumerate & check the
code. Enumerate & check is known as a brute force algorithm. We
will right a little loop that does this.

Farmyard Problem Code:

# 1 def solve(numLegs, numHeads):
# 2 for numChicks in range(0, numHeads + 1):
# 3 numPigs = numHeads – numChicks
# 4 totLegs = 4*numPigs + 2*numChicks
# 5 if totLegs == numLegs:
# 6 return (numPigs, numChicks)
# 7 return (None, None)

# 8 def barnYard():
# 9 heads = int(raw_input('Enter number of heads: '))    

#10 legs = int(raw_input('Enter number of legs: '))
#11 pigs, chickens = solve(legs, heads)
#12 if pigs == None:
#13 print 'There is no solution'
#14 else:
#15 print 'Number of pigs:', pigs
#16 print 'Number of chickens:', chickens

Line 1 def solve(numLegs, numHeads):
Defines "solve" as a function. Values are taken from numLegs and numHeads
Line 2 for numChicks in range(0, numHeads + 1):
For Loop. Use of a tuple. Defines the range(tuple) of the variables to
be used within the function.
Line 3 numPigs = numHeads – numChicks
Defines number of pigs as being num of heads – num of chickens.(Range is
defined by previous)
Line 4 totLegs = 4*numPigs + 2*numChicks
Defines the total number of legs as = 4(num Pigs) + 2(num Chicks)
Line 5 if totLegs == numLegs:
Boolean. Is the Total Legs equivelant to Number legs? True or False?
Line 6 return (numPigs, numChicks)
If True return the number of Pigs and Number of chickens to the interpreter.
If false go to line 3 until range as defined by tuple in line 2 is exhausted.
Line 7 return (None, None)
If boolean returns false until tuple is exhausted, return nothing to interpreter.

Line 8 def barnYard():
Defines barnYard as a function.
Line 9 heads = int(raw_input('Enter number of heads: '))    

Input take from use input as defined in line 1
Line 10 legs = int(raw_input('Enter number of legs: '))
Input take from use input as defined in line 1
Line 11 pigs, chickens = solve(legs, heads)
Calls results from solve function
Line 12 if pigs == None:

Boolean True or false? If pigs returned none, then all increments as defined in
tuple in line 2 were exhausted.
Line 13 print 'There is no solution'

True: No solution was found as their is not one.
Line 14 else:
If it was not true it has to be False.
Line 15 print 'Number of pigs:', pigs
Print to the screen number of pigs
Line 16 print 'Number of chickens:', chickens
Print to the screen the number of chickens.

Mathematical Equation of Farmyard Problem:
Line 1     20,56  (User Input)
Line 2     0       (Tuple
Range: 0 – 20)
Line 3     20 – 0 = 20
Line 4     4(20) + 2(0) = 80
Line 5     56 = 80 (Equivalent? True or False)

Line 2     1       (Tuple
Range: 0 – 20)
Line 3     20 – 1 = 19
Line 4     4(19) + 2(1) = 78
Line 5     56 = 78 (Equivalent? True or False)

Line 2     2       (Tuple
Range: 0 – 20)
Line 3     20 – 2 = 18
Line 4     4(18) + 2(2) = 76
Line 5     56 = 78 (Equivalent? True or False)

Line 2     3       (Tuple
Range: 0 – 20)
Line 3     20 – 3 = 17
Line 4     4(17) + 2(3) = 74
Line 5     56 = 78 (Equivalent? True or False)

Line 2     4       (Tuple
Range: 0 – 20)
Line 3     20 – 4 = 16
Line 4     4(19) + 2(4) = 72
Line 5     56 = 78 (Equivalent? True or False)

Line 2 increases to increment by 1 until either line 5 answers true to the Boolean,
or until the range as defined by the Tuple in line 2 is exhausted. This particular
problem turned results as the user input of 20 and 56 has a relevant answer.

Line 2     12       (Tuple
Range: 0 – 20)
Line 3     20 – 12 = 8
Line 4     4(8) + 2(12) = 56
Line 5     56 = 56 (Equivalent? True or False)
Lines 15 & 16     Print '8 Chickens    12 Pigs'

Recursion The idea of recursion is that you take a problem and
break down into a simpler version of the same problem, plus some steps you execute.
Base Case – Simplest possible solution
Inductive Step -Break same problem into a simpler version and
some other steps.

Example: Definition of US natural born citizen:
(Base Case) If you are born within the US, you are a US natural
born citizen.
(Inductive Step) If you were not born in the United States you
still may be a US natural born citizen even if you were born outside the United
States but only if both of your parents are citizens of the United States, and at
least one parent has lived in the United States.

Example in Code:
Testing a string for a Palindrome
Does it read the same right to left as it does left to right?
Base Case: Does the string have 0 or 1 element in it? Then its a Palindrome.
If it is longer then 1 what do you do?
Check the two end points, are they the same character?
If they are, then you just need to know if everything else in the middle is a Palindrome.

def isPalindrome(s):
"""Returns True if s is a palindrome and False otherwise"""
if len(s) <= 1: return True
else: return s[0] == s[-1] and isPalindrome(s[1:-1])

(More time needs to be spent within the Python GUI to better utilize class assignment).

def fib(x):
"""Return fibonacci of x, where x is a non-negative int"""
if x == 0 or x == 1: return 1
else: return fib(x-1) + fib(x-2)

Another example of recursion:
Dating back to the 1500's:
Fibonacci is the son of Nacci, apparently Nacci was a very friendly man.
Fibonacci Number: Take the sum of the first two numbers to create the total, the
next Fibonacci is the sum of the previous two, next Fibonacci is the sum of the
previous two.
Example (12 + 10 = 22) (10 +22 = 32) (32 + 22 = 54) (22 + 54 = 76) (76 + 54 = 130)
(54 + 130 = 184) etc, etc.
History of this is that Fibonacci was trying to count rabbits. The idea was that
rabbits can mate after one month they have 2 offspring, those offspring then have
offspring, the question was how many rabbits do you have at the end of 1 year, 2
years etc.
Pairs(0) = 1  
Pairs from 0 to 1. (Bought
2 rabbits!)
Pairs(1) = 1  
Pairs at beginning of month is 1.
Pairs (n) = Pairs(n-1) + Pairs(n-2)

Fibonacci Code:
def fib(x):
"""Return fibonacci of x, where x is a non-negative int"""
if x == 0 or x == 1: return 1
else: return fib(x-1) + fib(x-2)
An in depth review of this is needed before moving forward.

The above is my personal notes in regards to this class to help me in the
learning process.

  Related Posts