CS61A Lab 4: Recursion and Orders of Growth/Complexity

Week 2b, 2011

Iteration and Recursion

For the following 2 questions, write both an iterative solution (uses a while or for loop) and a recursive solution (no while or for loops).

1.) Write a function add_ten which takes 2 integers n and x, and returns x + n*10. DO NOT simply put return x + 10*n as the answer. Instead, try to write 2 versions of the function that implement it iteratively and recursively. We aren't testing you on your arithmetic skills.

2.) The greatest common divisor of two positive integers a and b is the largest integer which evenly divides both numbers (with no remainder). Euclid, a Greek mathematician in 300 BC, realized that the greatest common divisor of a and b is the smaller value if it evenly divides the larger value or the same as the greatest common divisor of the smaller value and the remainder of the larger value divided by the smaller value. So if a is greater than b and a is not divisible by b then:

gcd(a, b) == gcd(b, a % b)

Write the gcd function using Euclid's algorithm.

1.) 
def add_ten_iter(x, n):
    i, sum = 1, x
    while i <= n:
        sum += 10
        i += 1
    return 1
   
def add_ten_rec(x, n):
    if n == 0:
        return x
    return 10 + add_ten_rec(x, n-1)


def gcd_iter(a, b):
    if a < b:
        return gcd_iter(b, a)
    while a > b and not a % b == 0:
        a, b = b, a % b
    return b

def gcd_rec(a, b):
    if a < b:
        return gcd_rec(b, a)
    if a > b and not a % b == 0:
        return gcd_rec(b, a % b)
    return b

Recursion

Rewrite the following function recursively.

def func(a, b):
    i = 1
    while i <= a:
        print(i*b)
        i += 1

Now we're going to approximate the sine trigonometric function using 2 useful facts. One is that sin x is approximately equal to x as x gets small (for this problem, below 0.0001), and the other is the trigonometric identity

Using those two facts, write a function sin that returns the sine of a value in radians.
Consider an insect in a MxN grid. The insect starts at the top left corner, (0,0), and wants to end up at the bottom right corner, (M-1,N-1). The insect is only capable of moving right or down. Write a function count_paths that takes a grid length and width and returns the number of different paths the insect can take from the start to the goal. [There is an analytic solution to this problem, but try to answer it procedurally using recursion].

For example, the 2x2 grid has a total of two ways for the insect to move from the start to the goal. For the 3x3 grid, the insect has 6 different paths (only 3 are shown above).
Consider the following problem: How many different ways can we make change of $1.00, given half-dollars, quarters, dimes, nickels, and pennies? Assume you are given the function first_denomination(kinds) that returns the most valuable coin, given that you have kinds different coins. The code for first_denomination is given below.
```
def first_denomination(kinds):
    if kinds == 1:
        return 1
    elif kinds == 2:
        return 5
    elif kinds == 3:
        return 10
    elif kinds == 4:
        return 25
    elif kinds == 5:
        return 50
```
Write a function count_change(a, kinds) that returns the number of ways you can count an amount a (in cents) using kinds coins.

Hint: Your base cases have something to do with having no money (a == 0), or, either having no coins left or having an amount less than zero (kinds == 0 or a < 0). How are these the base cases?

1.)
def func_rec(a, b):
    if a == 0:
        return
    func_rec(a-1, b)
    print(a*b)
2.)def sine(x):
    if abs(x) < 0.0001:
        return x
    return (3*sine(x/3) - 4*pow(sine(x/3), 3))
3.)def paths(x, y):
    if x == 1 or y == 1:
        return 1
    return paths(x-1, y) + paths(x, y - 1)
4.)def count_change(a, kinds):
    if a == 0:
            return 1
    if a < 0 or kinds == 0:
        return 0
    return count_change(a, kinds - 1) + count_change(a - first_denomination(kinds), kinds)

Orders of Growth

Recall that the order of growth of a function expresses how long it takes for the function to run, and is defined in terms of the function's input sizes.

For example, let's say that we have the function get_x which is defined as follows:

def get_x(x):
    return x

get_x has one expression in it. That one expression takes the same amount of time to run, no matter what x is, or more importantly, how large x gets. This is called constant time, or O(1).

The main two ways that a function in your program will get a running time different than just constant time is through either iteration or recursion. Let's start with some iteration examples!

The (simple) way you figure out the running time of a particular while loop is to simply count the cost of each operation in the body of the while loop, and then multiply that cost by the number of times that the loop runs. For example, look at the following method with a loop in it:

def foo(n):
    i, sum = 1, 0
    while i <= n:
        sum,i = sum + i, i + 1
    return sum

This loop has one statement in it sum, i = sum + i, i + 1. This statement is considered to run in "constant time", as none of its operations rely on the size of the input. Individually, sum = sum + 1 and i = i + 1 are both constant time operations. However, when we're looking at order of growth, we don't add the times together and get O(2), we take the maximum of those 2 values and use that as the running time. In 61A, we are not concerned with how long primitive functions, such as addition, multiplication, and variable assignment, take in order to run - we are mainly concerned with "how many more times a loop is executed" or "how many more recursive calls" occur as the input increases. In this example, we execute the loop n times, and for each iteration, we only execute constant time operations, so we get an order of growth of O(n).

Here are a couple of basic functions, along with their running times. Try to understand why they have the given running time.

O(n)

def bar(n):
    i, a, b = 1, 1, 0
    while i <= n:
        a, b, i = a + b, a, i + 1
    return a

O(n^2)

def bar(n):
    sum = 0
    a, b = 0, 0
    while a < n:
        while b < n:
            sum += (a*b)
            b += 1
        b = 0
        a += 1
    return sum

Practice!

Now it's your turn! Try to figure out the running time of the following functions. If you have time, try to explain each one to your TA! For the last 3 questions, if you don't understand them, that's ok.

def bar(n):
      i, sum = 1, 0
      while i <= n:
          sum += biz(n)
          i += 1
      return sum

def biz(n):
    i, sum = 1, 0
    while i <= n:
        sum += i**3
        i += 1
    return sum

def baz(n):
      i, sum = 1, 0
      while i <= n:
          sum += bam(i)
          i += 1
      return sum

def bam(n):
    i, sum = 1, 0
    while i <= n:
        sum += i
        i += 1
    return sum

 def boom(n):
      sum = 0
      a, b = 1, 1
      while a <= n*n:
          while b <= n*n:
              sum += (a*b)
              b += 1
          b = 0
          a += 1
      return sum

4. (Challenging)

 def bonk(n):
      sum = 0
      while n >= 2:
          sum += n
          n = n / 2
      return sum

5. Very Challenging. This is much beyond what we expect you to know for the exam. This is here merely to challenge you.

 def boink(n):
      if n == 1:
          return 1
      sum = 0
      i = 1
      while i <= n:
          sum += boink(i)
          i += 1
      return sum

6. Analyze the order of growth of your sine function you wrote back in the Recursion section. Note: that problem was from SICP.

1.) O(n^2)
2.) O(n^2)
3.) O(n^4)
4.) O(log(n))
5.) O(2^n)
6.) O(log(n)), assuming your code looks like:

def sin(angle):
    if abs(angle) <= 0.1:
        return angle
    else:
        res = sin(angle / 3)
        return 3*res - 4*(res**3)

But, if your solution was the naive tree-recursive way, then,
the running time is: O(2^(log_3(n))) = O(n^(log(3))) ~ O(n^1.58)

def sin(angle):
    if abs(angle) <= 0.1:
        return angle
    else:
        return 3*sin(angle / 3) - 4*(sin(angle / 3)**3)

For the count_change problem, you can check your answer here. Try to understand this problem; it's a useful learning tool to understand more complex recursion. x