CS61A Lab 4: Recursion, and General Debugging

Week 4, 2013

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

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)

Debugging

Whenever Python encouters a bug in your code, it will print a list of error messages. This printed statement is known as a traceback. A traceback might look scary to the untrained eye, but it is actually a very useful debugging tool!

A sample traceback looks like this:
```
Traceback (most recent call last):
  File "bug1.py", line 22, in func
      g = bug()
  File "bug2.py", line 3, in bug
      buggy = buggy + 1
NameError: name 'buggy' is not defined
```
A traceback displays all the function calls that led up to the error. You can think of this in terms of an environment diagram where the traceback displays all of the frames that we have created up to this point that have not returned a value. Notice that the message tells you that the "most recent call" is displayed "last", at the bottom of the message. We can think of this "last" call as being the current frame that we are in.

You may have noticed that the traceback is organized in "couplets." Each couplet is composed of two lines: the location; and the actual code

The location is the first line in the couplet:
```
  File "file name", line number, in function name
```
This line provides you with three bits of information:
- file name: the name of the file where this function call is located
- line number: the line number in the file where the error is located
- function name: the name of the function that houses the error
From this line alone, you should be able to locate the line where the error occurs, in case you need reference it in more detail.

The second line in the couplet is the code line:
```
    line of code here
```
This line allows you to see the piece of code that triggered the error just by looking at the traceback. That way, you can quickly reference the code and guess why the error occured.

The very last line in a traceback is the error type:
```
    Error type: Error message
```
The error type is usually named to be descriptive (such as SyntaxError or IndexError). The error message is a more detailed (but still brief) description of the error.

Now that you know how to read a traceback, you are well-equipped to handle any bugs that come your way. The following are some common bugs that occur frequently (many of you might have seen them before). Try to debug the code!

You can copy the starter code (for the debugging and list portions of the lab) into your current directory to produce the traceback.
```
cp ~cs61a/lib/lab/lab04/lab4.py .
```
Feel free to do so, but copying and pasting from a webpage doesn't always yield the results you would expect!
```
def one(mississippi):
    """
    >>> one(1)
    1
    >>> one(2)
    4
    >>> one(3)
    6
    """
    if mississippi == 1:
        return misssissippi
    elif mississippi == 2:
        return 2 + mississippi
    elif mississippi = 3:
        return 3 + mississippi

def two(two):
    """
    >>> two(5)
    15
    >>> two(6)
    18
    """
    one = two
    two = three
    three = one
    return three + two + one

def three(num):
    """
    >>> three(5)
    15
    >>> three(6)
    21
    """
    i, sum = 0, 0
    while num > i:
        sum += num
    return sum

def four(num):
    """
    >>> four(5)
    16
    >>> four(6)
    32
    """
    if num == 1:
        return num
    return four(num - 1) + four(num)
```
```
def one(mississippi):
    if mississippi == 1:
        return misssissippi                 # extra 's' in mississippi
    elif mississippi == 2:
        return 2 + mississippi
    elif mississippi = 3:                   # should be ==, not =
        return 3 + mississippi

def two(two):
    one = two
    two = three                             # the variable three is undefined
    three = one
    return three + two + one

def three(num):
    i, sum = 0, 0
    while num > i:
        sum += num                          # our loop never terminates because we don't increment i/decrement num!
    return sum

def four(num):
    if num == 1:
        return num
    return four(num - 1) + four(num - 1)    # second recursive call doesn't decrement num, this yields infinite recursion!
      
```
Finally, you should almost always run the doctests we provide you from the terminal, instead of copying and pasting the tests into an interpreter. This avoids typing mistakes, is a lot faster, and achieves the same result.
For this example, we are going to be debugging some code that has been given to us, as well as writing some test cases to make sure that the function is doing what we want it to do. Copy the template for this file by running the following from your terminal:
```
  cp ~cs61a/lib/lab/lab04/anagrams.py .
```
Let's open the file in your favorite text editor (probably Emacs if you're on the lab machines) and try to understand the code. You do not have to understand how the function remove(letter, word) works; we will learn that later, but you should try to understand what the rest of the functions are doing based off of the docstrings. We're given several functions that will help us find out whether two words are anagrams of one another, that is, we want to know if we can use all the original letters of w1 exactly once to form w2 and vice versa. We can assume that all of the functions written below contains work as described and that they work correctly. Our job is to figure out if the contains function works correctly, and if it does not, fix it so that it does. Let's open our file in an interactive Python session by running:
```
  python3 -i anagrams.py
```
Play around with the functions that we gave you and verify that they do indeed work. It also might be a good idea to run our doctests using the command: python3 -m doctest anagrams.py.
```
**********************************************************************
File "./anagrams_bad.py", line 60, in anagrams_bad.anagrams
Failed example:
    anagrams("domo", "doom") # but for the record, Domo is awesome.
Expected:
    True
Got:
    False
**********************************************************************
File "./anagrams_bad.py", line 4, in anagrams_bad.contains
Failed example:
    contains("cute", "computer")
Expected:
    True
Got:
    False
**********************************************************************
File "./anagrams_bad.py", line 8, in anagrams_bad.contains
Failed example:
    contains("car", "race")
Expected:
    True
Got:
    False
**********************************************************************
File "./anagrams_bad.py", line 10, in anagrams_bad.contains
Failed example:
    contains("hi", "high")
Expected:
    True
Got:
    False
**********************************************************************
```
Whoa, we are failing 4 doctests, not good, not good at all. Let's take a closer look at why. In the three doctests for contains, we see that the contains is returning False when it is expecting True. Take a couple of minutes to think of additional test cases that would return False when we expect True and vice versa. Compare test cases with your neighbors to see if there are any that either of you missed.

Now that we have found a set of test cases that are yielding incorrect results, we can start to figure out if we need to change existing base cases, add more base cases, or to alter our recursive case(s). Let's take a closer look at our base cases. Our function's base cases only seem to return False! That means that no matter what we input, this function will always return False. That's not what we want. Add a base case that might help alleviate this problem.

Hopefully, we found an edge case in the previous exercise and now our function correctly returns the value that we want. However, all 4 of our doctests are still failing! We should take a look at our recursive cases. Remember in recursion, the idea is that we should always be working towards our base case. Otherwise, our function will continuously call itself with the same input causing our function to fall into what we call "infinite recursion". To avoid infinite recursion, always make sure that the input is working towards satisfying the base case. Right now, our function is continuously checking to see if the first letter of w1 is in w2. If it is, we are recursively calling contains while removing the first letter of w1 from w2. Walk through this process using the last doctest, contains("hi", "high"), as an example to see what exactly the code does. Writing out each function call on a piece of paper has been said to help. Are we recursively calling contains with the desired inputs? See if you can fix the recursive case. If you are having trouble, talk with your neighbors or lab assistants to see if they can point you in the right direction.

Great, you fixed the recursive case! Let's run the doctests again to make sure everything is passing.
```
def contains(w1, w2):
    if len(w1) == 0:
        return True
    if len(w2) == 0:
        return False
    if has_letter(first(w1), w2):
        return contains(rest(w1), remove(first(w1), w2))
    return False
      
```
Thanks to your awesome TA, Albert, here is a pdf of general debugging tips. This guide will help you read the traceback message, decrypt error messages, and identify common errors that Python programmers run into often. Make sure you read through this guide; it will make writing and debugging programs much easier!

Extra Recursion Examples

Given the following functions first(word), second(word), and rest(word) see if you can define a recursive function count_hi(phrase) that takes in a string of any length and returns the number of times the phrase "hi" appears within.
```
def first(word):
    return word[0]
        
def second(word):
    return word[1]
            
def rest(word):
    return word[1:]
  
```
Here are some doctests to help you out:
```
>>> count_hi("hihihihi")
4
>>> count_hi("hhjfdkfj")
0
>>> count_hi("")
0
>>> count_hi("hih")
1
  
```
Given a function is_vowel(char) that takes in a single character and returns a boolean stating whether or not it is a vowel or not, define a recursive function remove_vowels(word) that removes all vowels from the word. Feel free to use the functions first(word) or rest(word) from the previous problem.
```
def is_vowel(char):
    return char == 'a' or char == 'e' or char == 'i' or char =='o' or char == 'u'
  
```
Here are a few doctests to help you out, although, the functionality of this code should be somewhat obvious by the name...
```
>>> remove_vowels("hi my name is mark")
'h my nm s mrk'
>>> remove_vowels("aeiou")
''
>>> remove_vowels("is y a vowel?")
's y  vwl?'
  
```
By now you're an expert on recursion right? Let's write a recursive function pair_star(phrase) that takes in a phrase and returns the same phrase where identical characters that are adjacent in the original phrase are separated with the character "*". Phrases without identical characters adjacent to one another should just return the original string. You can concatenate two strings together using the "+" operator. For example, "hello" + " " + "world" will yield the result 'hello world'
```
>>> pair_star("hiihhi")
'hi*ih*hi'
>>> pair_star("woodlands have squirrels")
'wo*odlands have squir*rels'
>>> pair_star("h")
'h'
  
```

1.)
def count_hi(phrase):
    if len(phrase) <= 1:
        return 0
    elif first(phrase) == 'h' and second(phrase) == 'i':
        return 1 + count_hi(rest(phrase))
    else:
        return count_hi(rest(phrase))
        
2.)
def remove_vowels(word):
    if word == '':
        return ''
    elif is_vowel(first(word)):
        return remove_vowels(rest(word))
    else:
        return first(word) + remove_vowels(rest(word))
        
3.)
def pair_star(phrase):
    if len(phrase) <= 1:
        return phrase
    elif first(phrase) == second(phrase):
        return first(phrase) + "*" + pair_star(rest(phrase))
    else:
        return first(phrase) + pair_star(rest(phrase))