Python Fundamentals

Authors: Tom Dunham
Date: 2009-03-31

Elements of Programming

A programming language gives us three things:

Expressions

http://farm1.static.flickr.com/46/145269819_c7a1ca7439.jpg?v=0
>>> 256
256
>>> 137 + 349
486
>>> 5 * 99
495
>>> 10 / 5
2

Expressions (2)

You can combine expressions

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

Assignment

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

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

Assignment (2)

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

Review

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

Functions

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

Functions (2)

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

Conditionals

Allow us to choose

We can now define the absolute value function:

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

Exercise

See handout

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

  1. 10

  2. 5 + 3 + 4

  3. 9 - 1

  4. 6 / 2

  5. (2 * 4) + (4 - 6)

  6. a = 3

  7. b = a + 1

  8. a + b + a * b

  9. a == b

  10. if b > a and b < a * b:

    print b

    else:

    print a

  11. 5 / 2

    Is that the value you expected?

  12. 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
    
  13. What is wrong with this (Python) expression? 1 + 1 = 2

  14. Write a function that takes two arguments and returns their mean.

Booleans

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

Loops

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

http://farm4.static.flickr.com/3499/3223576566_16d0172e21.jpg?v=0

While

What does this print?

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

For

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

Recursion

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

Factorials

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)!

Factorials (while)

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

Factorials (for)

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

Factorials (recursive)

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

Exercise

See handout

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

  1. What will this print?

    a = 10
    while a < 100:
        print "a"
    
  2. When will the program in question 1 terminate?

  3. 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
    
  4. 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

    1. A while loop
    2. A for loop
    3. Recursion
  5. 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:

    1. Take a guess at the root
    2. Test if the guess is good enough
    3. 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.