# Python Fundamentals

Authors: Tom Dunham 2009-03-31

# Elements of Programming

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

# Expressions ```>>> 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

• 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

# Functions

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

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

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