Reviewing Mutation and Aliasing

The following code works as expected, and prints [[1,4], [2,5], [3,6]]

def trans(given):
  nrows = len(given)
  ncols = len(given[0])
  matrix = [[0,0],[0,0],[0,0]]
  for i in range(ncols):
    for j in range(nrows):
      matrix[i][j] = given[j][i]
  return matrix

a = [[1,2,3],[4,5,6]]

However, the following code prints [[3,6], [3,6], [3,6]]:

def trans(given):
  nrows = len(given)
  ncols = len(given[0])
  #matrix = [[0,0],[0,0],[0,0]] #commented this out and replaced it with the line below
  matrix = [[0]*nrows]*ncols
  for i in range(ncols):
    for j in range(nrows):
      matrix[i][j] = given[j][i]
  return matrix

a = [[1,2,3],[4,5,6]]

Why? Because the multiplication with ncols simply duplicates the references to the same list.

Here is the correct version:

def trans(given):
  nrows = len(given)
  ncols = len(given[0])
  matrix = [[0 for _ in range(nrows)] for _ in range(ncols)]  #initialize as separate lists for each row
  for i in range(ncols):
    for j in range(nrows):
      matrix[i][j] = given[j][i]
  return matrix

a = [[1,2,3],[4,5,6]]

It is worth emphasizing again that there is a subtle difference between:

L.append(item) (mutation)
L = L + [item] (re-binding)

In the first case, the original list (associated with L) is getting modified; while in the second case, a new list is getting created and L is then associated with the new list.

Recursion

What is recursion?

Algorithmically: a way to design solutions to problems by divide-and-conquer or decrease-and-conquer.
- Reduce a problem to simpler versions of the same problem.
Semantically: a programming technique where a function calls itself.
- in programming, goal is to NOT have infinite recursion
  - must have one or more base cases that are easy to solve.
  - must solve the same problem on some other input with the goal of simplifying the larger problem input.

Iterative algorithms so far

looping constructs lead to iterative algorithms.
can capture computation in a state of state variables that update on each iteration through loop.

Multiplication: Iterative Solution

"multiply a*b" is equivalent to "add a to itself b times"
capture state by
- an iteration number i starts at b
```
i <- i-1 and stop when 0
```
- a current value of computation (result)
```
result <- result + a
```

def mult_iter(a, b):
  result = 0
  while b > 0:   #iteration
    result += a     #current value of computation: a running sum
    b -= 1          #current value of iteration variable
  return result

Multiplication: Recursive Solution

recursive step: think how to reduce problem to a simpler or smaller version of the same problem.

a*b = a + a + ... + a     (b times)
    = a + (a + ... + a)   (b-1 times for the value in the parentheses)
    = a + a*(b-1)         (the latter term has the same structure as the original problem)

base case: keep reducing problem until reach a simple case that can be solved directly when b=1, a*b=a.

def mult(a, b):
  if b == 1:         # base case
    return a
  else:
    return a + mult(a, b-1)  # recursive step

Factorial

n! = n*(n-1)*(n-2)*...*1

for what n do we know the factorial?
```
if n == 1:
  return 1  #base case
```
how to reproduce the problem? Rewrite in terms of something simpler to reach the base case
```
else:
  return n*factorial(n-1)    #recursive step
```

Recursive function scope example

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

print(fact(4))

Global scope has fact -> some code
fact scope (call with n=4) has n -> 4
fact scope (call with n=3) has n -> 3
fact scope (call with n=2) has n -> 2
fact scope (call with n=1) has n -> 1

Order of computation:

fact scope (call with n=1) returns 1
fact scope (call with n=2) returns 2*fact(1)=2*1=2
fact scope (call with n=3) returns 3*fact(2)=3*2=6
fact scope (call with n=4) returns 4*fact(3)=4*6=24
global scope prints fact(4)=24

Some observations:

each recursive call to a function creates its own scope/environment.
bindings of variables in a scope are not changed by recursive call.
- using the same variable names but they are different objects in separate scopes.
flow of control passes back to previous scope once function call returns value.

Iteration vs. Recursion.
Iteration:

def factorial_iter(n):
  prod = 1
  for i in range(1,n+1):
    prod *= i
  return prod

Recursion:

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

recursion may be simpler, more intuitive
recursion may be efficient from programmer's point of view
recursion may not be efficient from computer's point of view