## 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.

**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.

return x

**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

print.

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

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

Line 3 numPigs = numHeads – numChicks

defined by previous)

**Defines the total number of legs as = 4(num Pigs) + 2(num Chicks)**

Line 4 totLegs = 4*numPigs + 2*numChicks

Line 4 totLegs = 4*numPigs + 2*numChicks

**Boolean. Is the Total Legs equivelant to Number legs? True or False?**

Line 5 if totLegs == numLegs:

Line 5 if totLegs == numLegs:

**If True return the number of Pigs and Number of chickens to the interpreter.**

Line 6 return (numPigs, numChicks)

Line 6 return (numPigs, numChicks)

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 7 return (None, None)

**Line 8 def barnYard():
**Defines barnYard as a function.

**Input take from use input as defined in line 1**

Line 9 heads = int(raw_input('Enter number of heads: '))

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: '))

Line 10 legs = int(raw_input('Enter number of legs: '))

**Calls results from solve function**

Line 11 pigs, chickens = solve(legs, heads)

Line 11 pigs, chickens = solve(legs, heads)

Line 12 if pigs == None:

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'

Line 13 print 'There is no solution'

True: No solution was found as their is not one.

**If it was not true it has to be False.**

Line 14 else:

Line 14 else:

**Print to the screen number of pigs**

Line 15 print 'Number of pigs:', pigs

Line 15 print 'Number of pigs:', pigs

**Print to the screen the number of chickens.**

Line 16 print 'Number of chickens:', chickens

Line 16 print 'Number of chickens:', 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.

**Fibonacci:
Pairs(0) = 1 **Pairs from 0

**to 1. (Bought**

**2 rabbits!**

**)**

Pairs(1) = 1Pairs at beginning of month is 1.

Pairs(1) = 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.*

MAY