Week 5: Exercises

1. Local and Global

What will this program print?

a = 2
b = 3

def foo():
  a = b + 1
  a = a + 1
  return a

def bar():
  global b
  b = a + 3
  return b

def baz():
  return a + b

def thud():
  a = b + 1
  b = a + 1
  return a

print(foo())
print(bar())
print(baz())

print(thud())

2. Append

Write a function append() that takes a variable number of arguments. Each argument should be a sequence, such as a list. The function should return a sequence formed by concatenating all of the sequences. For example:

>>> append([1, 2], [5, 6], [8, 9])
[1, 2, 5, 6, 8, 9]
>>> append()
[]

3. Max

Write a function my_max() that takes one or more arguments. If there is just one argument, it should be a sequence, and my_max() should return the maximum value in the sequence. Otherwise, each argument should be a value, and my_max() should return the maximum of these values. For example:

>>> max([2, 4, 6])
6
>>> max(2, 4, 6)
6

4. No Zeroes, Recursively

Write a function no_zeroes(n) that takes an integer n and returns an integer formed by removing all zeroes from the end of n's decimal representation. For example:

>>> no_zeroes(54000)
54
>>> no_zeroes(2256)
2256

As a special case, no_zeroes(0) = 0.

You may not use any loops in your solution, so you will need to write the function recursively.

5. Recursive Power

a) Write a recursive function is_pow_of_2(n) that returns True if n is a power of 2.

b) Generalize the function: write a recursive function is_pow_of_k(k, n) that returns True if n is a power of k.

6. Recursive Sum

Write a function sum(a, i, j) that computes the sum of the values in the range a[i:j]. You may not use any loops or call the built-in sum() function, so you will need to use recursion.

7. Recursive Max

Write a function max(a, i, j) that computes the maximum value in the range a[i:j]. You may not use any loops or call the built-in max() function, so you will need to use recursion.

8. Recursive Binary Search

Write a function search(a, x) that takes a sorted array a and a value x to search for in the array. It should return True if x is present in the array, otherwise false. Use a binary search. Do not use any loops; instead, write a recursive helper function.

9. Recursive Multiplication

Write a recursive function mul(a, b) that returns the product (a * b) for positive integers a and b. You may use the built-in addition operator (+), but not the multiplication operator (*).

10. Same as the First

Use recursion to write a function same_as_first(a) that returns the number of integers in an array a that are equal to its first element.

11. Lots of References

Recall that a[:] makes a copy of the list a. It's the same as a[0:len(a)], or as a.copy().

What will this program print? Why?

def bar(a):
    for i in range(len(a)):
        a[i] += 1
        a = a[:]

def foo(a):
    for b in a + a[:]:
        bar(b)
        bar(b[:])

m = [[1, 2], [3, 4]]
foo(m)
print(m)