Authors: | Tom Dunham |
---|---|

Date: | 2009-03-31 |

A programming language gives us three things:

*expressions*- the simplest things the language "understands"*means of combination*- through which we build complex elements from simpler ones*means of abstraction*- which allow us to name and manipulate these compound elements as units

>>> 256 256

>>> 137 + 349 486

>>> 5 * 99 495

>>> 10 / 5 2

You can combine expressions

>>> 21 + 35 + 12 + 7 75 >>> 3 * (2 * 4 + (3 + 5)) + ((10 - 7) + 6) 57

You give something a name by assigning it to that name.

>>> size = 2 >>> size 2 >>> size * 5 10

>>> size = size + 2 >>> size 4 >>> pi = 3.1415926535897931 >>> pi 3.1415926535897931

This is also called *binding* a name to a value.

Assignment is such a fundamental part of programming that there are a lot of different ways to describe what's going on here.

The expression `size = 2` can be read:

- Bind the name
`size`to the value`2` `size`takes the value`2`- The variable
`size`is assigned the value`2`

Note also that the meaning of `=` to Python is not what you are
familiar with from maths. In maths, `=` is a test for
equality. In Python, `=` binds a name to a value; `==` is the
test for equality.

We've now seen some of the elements of programming languages

- Numbers and arithmetic are primitive expressions
- Expressions can be nested to form more complex expressions
- Names can be associated with values to provide a limited means of abstraction

>>> def square(x): ... return x * x

`def`binds the name`square`to the operation`x`is a parameter, which gives the thing to be squared a local name- the indented
*block*of lines perform the operation `return`passes the value of applying the procedure to it's parameters back to the caller.

>>> square(2) 4 >>> square(2 + 4) 36

Now we can use `square` as a building block

>>> def sum_of_squares(x, y): ... return square(x) + square(y) ... >>> sum_of_squares(3, 4) 25

Allow us to *choose*

We can now define the absolute value function:

>>> def abs(x): ... if x < 0: ... return -x ... else: ... return x

See handout

Evaluate the following expressions in the interpreter (in the given order)

10

5 + 3 + 4

9 - 1

6 / 2

(2 * 4) + (4 - 6)

a = 3

b = a + 1

a + b + a * b

a == b

- if b > a and b < a * b:
print b

- else:
print a

5 / 2

Is that the value you expected?

5.0 / 2

You see this behavior because Python implements "floor division" for integers (the result is rounded down to the nearest integer). This is unsurprising for people familiar with the C programming language, but quite a shock for most others.

Because of this unintuitive behavior, it's unusual to see the

`/`operator applied to two integers (or two names bound to integer values). Normally, division is written:x * 1.0 / y

And deliberate floor division is written:

x // y

What is wrong with this (Python) expression?

`1 + 1 = 2`Write a function that takes two arguments and returns their mean.

Python supports a number of boolean operations, though the notation may not be what you are used to:

>>> 2 < 4 True >>> 4 >= pi > 2 True >>> not 2 == 1 True |
>>> 2 == 2 True >>> 2 != pi True |

Computers are very good at repetitive tasks. Python offers two main ways to repeat yourself.

`while`loops execute a block of code until a condition is true`for`loops execute a block of code for each element in a sequence, stopping when the sequence is exhausted

What does this print?

def countdown(n): while n > 0: print n n = n-1 print "Blastoff!"

countdown(10)

For loops process sequences.

`range` is a function that returns a `list` (more on these later).

>>> range(1, 10) [1, 2, 3, 4, 5, 6, 7, 8, 9]

What does this print?

for i in range(0, 10): print i

Loops express *iteration* (repetition of a process). This can also be
done through *recursion*

def countdown(x): if x == 0: print "Blastoff" else: print x countdown(x-1)

Calling a procedure recursively and using a loop are two different ways to express the same thing.

Wikipedia has a good explanation of recursion:

To understand recursion, one must recognize the distinction between a procedure and the running of a procedure. A procedure is a set of steps that are to be taken based on a set of rules. The running of a procedure involves actually following the rules and performing the steps.

http://en.wikipedia.org/wiki/Recursion#Recursion_in_plain_English

Often you can write the same loop in several ways.

We're going to write a function to calculate factorials using
`while` loops, `for` loops and recursion.

n = 1 → n! = 1

n > 1 → n! = n(n-1)!

def fac_while(x): fac = 1 count = 1 while count <= x: fac = fac * count count = count + 1 return fac

def fact_for(n): fac = 1 for i in range(1, n+1): fac = fac * i return fac

def fac_r(n): if n == 1: return 1 else: return n * fac_r(n-1)

See handout

Do the first three exercises *without* using the computer, then check
your answers.

What will this print?

a = 10 while a < 100: print "a"

When will the program in question 1 terminate?

What will the following program print?

The

`%`operator in Python performs modulo division (return the remainder after integer division).a = 2 while a % 9 != 0: if a % 3 == 0: print 0 if a % 7 == 0: print 7 a = a -1 a = a + 2

Fibonacci numbers

Leonardo of Pisa (aka Fibonacci) used this sequence of numbers in 1202 to model the population of rabbits.

Definition

f(0) == 0 f(1) == 1 f(n) == f(n-2) + f(n-1)

The first 20 elements of the Fibonacci sequence are

F0

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

F11

F12

F13

F14

F15

F16

F17

F18

F19

F20

0

1

1

2

3

5

8

13

21

34

55

89

144

233

377

610

987

1597

2584

4181

6765

(For more see: http://www.research.att.com/~njas/sequences/A000045)

Write functions to calculate

`fib(n)`using- A
`while`loop - A
`for`loop - Recursion

- A
Square Roots by Newton's Method

Write a procedure

`sqrt`that uses the Newton-Raphson method to approximate the square root of it's parameter (`x`).The Newton-Raphson method states that a guess (

`y`) of the root of`x`can be improved by averaging`y`and`x/y`.One way to apply the method is as follows:

- Take a guess at the root
- Test if the guess is good enough
- If not, your next guess is the average of your current guess and the number you are attempting to find the root of divided by your last guess.

*Hints*You'll probably want to use either a

`while`loop or recursion. Either way, you'll need to test if you are close enough to the result, and you may want to write a function to do this. For our purposes, within 0.001 is good enough.We defined some maths functions in the lectures and in previous exercises; you can use them here.

If you are trying to form a recursive solution, take note of the similarities between the recursive examples we have studied so far. Notice that they all contain an

`if`with a test that chooses between a terminal case (which means that the instructions don't have to be repeated again), and the recursive case (which means the procedure will be repeated to bring us closer to the solution).Once you've solved the problem using one approach, try the other one (so if you used a loop, try to solve the problem recursively). Try to look where you duplicate code, move that into functions, and call the functions rather than having it in the file twice.