Week 11: Recursion

Lecture 4/13/2020

Agenda:

List slice syntax
Recursion intro

Slicing

Slicing syntax allows us to extract sublists from lists or substings from strings.

"""
Examples of Python slicing
"""

def main():
    L = list(range(1,10,2))
    print(L)
    subList = L[2:4] # extract sublist from index 2 to index (4-1)
    print(subList)

    subList = L[:4] # extract from the start of the list to (4-1)
    print(subList)

    subList = L[2:] # extract from index 2 to the end of the list
    print(subList)

    subList = L[:] # copies the whole list
    print(subList)

    subList = L[1:3:2] # extracts L[start:end:step]
    print(subList)

    subList = L[1:4:2] # extracts L[start:end:step]
    print(subList)

    subList = L[0:4:2] # extracts L[start:end:step]
    print(subList)

    value = L[-1] # last item in the list (e.g. len(L)-1)
    print(value)

    value = L[-2] # second to last item in the list (e.g. len(L)-2)
    print(value)

    subList = L[:-2] # from beginning to third to last item in the list (e.g. len(L)-2)
    print(subList)

    subList = L[-2:] # to from second to last item to end of list
    print(subList)

main()

`sliceFileExt.py`

Write a function that uses slice to return the file extension of a filename

$ python3 sliceFileExt.py
Enter a filename: test.png
Extension: png

$ python3 sliceFileExt.py
Enter a filename: test.py
Extension: py

$ python3 sliceFileExt.py
Enter a filename: document
Extension:

$ python3 sliceFileExt.py
Enter a filename: test.3.2.png
Extension: png

There are several possible solutions

def extractExtension(filename):
    """
    Parameter (str): a filename
    Return (str): the file extension
    """
    number = len(filename)
    for i in range(len(filename)):
        if filename[i] == ".":
            number = i
    extension = filename[i+1:]
    return extension

def extractExtension(filename):
    """
    Parameter (str): a filename
    Return (str): the file extension
    """
    if "." not in filename:
        return ""
    else:
        tokens = filename.split(".")
        return tokens[-1]

def extractExtension(filename):
    """
    Parameter (str): a filename
    Return (str): the file extension
    """
    for i in range(len(filename)-1, 0, -1):
        if filename[i] == ".":
            return filename[i+1:]
    return ""

def extractExtension(filename):
    """
    Parameter (str): a filename
    Return (str): the file extension
    """
    tokens = filename.split(".")
    if len(tokens) > 1:
       return tokens[-1]

    return ""

Recursion

Recursion is a way of solving self-similar problems
We’re used to functions which call other functions, but it’s also possible for a function to call itself! — A recursive function is a function that calls itself
Recursion functions are conceptually similar to a loop — every time the function calls itself, it repeats a set of commands

Two-important components to a recursive function

Base case: When should we stop recursing? Recursion rule: How do we recurse?

`rprintList.py`

Below is the example from class, running in Python tutor

Click here to see the demo in Python tutor

At the end of program, the function stack looks like this.

Python tutor draws function stacks from top to bottom but in class, we draw them from the bottom up.

When we use slicing to get a new sublist, a new list is created on the heap!

Lecture 4/15/2020

https://youtu.be/XacZbYkvjwk

Agenda:

Recursion examples

`sum.py`

def sumN(n):
    total = 0
    for i in range(n+1):
        total += i
    return total

def rsumN(n):
    # base case
    if n == 0:
        return 0

    # recursion rule
    subSum = rsumN(n-1)
    sum = n + subSum
    return sum

def main():
    print(sumN(10))
    print(rsumN(10))

main()

`mulList.py`

I added print statements to main() so we can see the execution

I changed the code in main() so that calling rmulList on an empty list returns 1 and not 0. This simplifies the code so we do not need a special case for the empty list.

Programmers can use assert to put tests into their code. If the value passed to an assert is False, the program aborts with an AssertionError. Using assert draws attention to bugs and errors during development.

def mulList(L):
    prod = 1
    for i in range(len(L)):
       prod *= L[i]
    return prod

def rmulList(L):
    if len(L) == 0:
        return 1.0

    subProd = rmulList(L[1:])
    prod = L[0] * subProd
    return prod

def main():
    L = [3, 5, 1, 2, 4]
    print(L)
    print("Product: ", rmulList(L))

    assert(mulList(L) == 120)
    assert(rmulList(L) == 120)
    assert(rmulList([3]) == 3)
    assert(rmulList([]) == 1)

main()

`allEven.py`

main() has been extended to contain print statements so we can see the program’s execution.

"""
Write iterative and recursive functions to check if a list has only even numbers
"""

def allEven(L):
    for i in range(len(L)):
       if L[i] % 2 == 1: # L[i] is odd
          return False
    return True

def rallEven(L):
    if len(L) == 0:
        return True
    # recursive rule
    # return T if first element is even
    #   AND rallEvent is T for the rest of the list
    subBool = rallEven(L[1:])
    if L[0] % 2 == 0:
        firstIsEven = True
    else:
        firstIsEven = False

    return firstIsEven and subBool

def main():
    L = [3, 5, 1, 2, 4]
    assert(allEven(L) == False)
    assert(rallEven(L) == False)
    print(L)
    print(rallEven(L))

    L = [-2, 4, 0, 2, 4]
    assert(rallEven(L) == True)
    assert(rallEven(L) == True)
    print(L)
    print(rallEven(L))

    assert(allEven([]) == True)
    assert(rallEven([]) == True)
    print(L)
    print(rallEven(L))

main()

rallEven can be written more concisely as follows:

def rallEven(L):
    if len(L) == 0:
        return True

    subBool = rallEven(L[1:])
    firstIsEven = (L[0] % 2 == 0) # result of bool expression is stored in variable
    return firstIsEven and subBool

`hello.py`

"""
Print "hello" n times
"""

def hello(n):
    for i in range(n):
        print("hello")

def rhello(n):
    if n == 0:
        return

    print("hello")
    rhello(n-1)

def main():
    hello(3)
    print("-"*10)
    rhello(3)

main()

`strlen.py`

"""
Write iterative and recursive functions to the length of a string
"""

def strlen(text):
    total = 0
    for i in range(len(text)):
       total += 1
    return total

def rstrlen(text):
    # base case
    if text == "":
        return 0

    # rule: length = one + the length of the rest of the list
    subLen = rstrlen(text[1:])
    len = 1 + subLen
    return len

def main():
    print("", rstrlen(""))
    print("abba", rstrlen("abba"))
    print("cat", rstrlen("cat"))
    print("hello", rstrlen("hello"))

main()

4/17/2020

https://youtu.be/W6GROkQVHDk

Agenda:

Visualizing recursion
More recursion practice
Recursive binary search

Notes:

Visualizations of the recursive algorithms covered in class. These notes have been extended to include more examples from this week’s examples. Try to visualize the more of the Examples on your own!

`countLetter.py`

"""
Write iterative and recursive functions to count the number of a letter in a
string
"""

def countLetter(phrase, letter):
    total = 0
    for i in range(len(phrase)):
        char = phrase[i]
        if char == letter:
            total = total + 1
    return total


def rcountLetter(phrase, letter):
    if len(phrase) == 0:
        return 0

    if phrase[0] == letter:
        return 1 + rcountLetter(phrase[1:], letter)
    else:
        return rcountLetter(phrase[1:], letter)

def main():
    phrase = "hello"

    letter = "l"
    print(phrase, letter, countLetter(phrase, letter))
    print(phrase, letter, rcountLetter(phrase, letter))

    letter = "e"
    print(phrase, letter, countLetter(phrase, letter))
    print(phrase, letter, rcountLetter(phrase, letter))

    letter = "x"
    print(phrase, letter, countLetter(phrase, letter))
    print(phrase, letter, rcountLetter(phrase, letter))

main()

`baddpassword.py`

"""
Replace all "e"'s with "3"'s
"""

def badpassword(text):
    passwd = ""
    for i in range(len(text)):
       if text[i] == "e":
          passwd += "3"
       else:
          passwd += text[i]
    return passwd

def rbadpassword(text):
    # base case
    if text == "":
        return ""

    # rule: test first character
    # and then append rbadpassword on rest of text
    if text[0] == "e":
        return "3" + rbadpassword(text[1:])
    else:
        return text[0] + rbadpassword(text[1:])

def main():
    print(badpassword("fee"))
    print(rbadpassword("fee"))
    print(badpassword("elephant"))
    print(rbadpassword("elephant"))


main()

`isSymmetric.py`

def drawHistogram(values):
    print("---")
    for i in range(len(values)):
        val = values[i]
        print("#"*val)
    print("---")

def isSymmetric(L):
    # Base case when L has even number of elements
    if len(L) == 0:
        return True

    # Base case when L has an odd number of elements
    if len(L) == 1:
        return True

    # rule: return T if first and last elements match
    #    AND the rest of the list is isSymmetric
    firstLastMatch = (L[0] == L[-1])
    return firstLastMatch and isSymmetric(L[1:-1])

def main():

    Tests = [[1,2,5,2,1],
             [5,2,5,2,1],
             [1],
             [],
             [2,2,2,2],
             [2,3],
             [2,3,3,2],
             [3,1,1,3]
             ]

    for L in Tests:
        drawHistogram(L)
        print("isSymmetric?", isSymmetric(L))

main()

recursive binary search

def rbinsearch(x, L):
    if len(L) == 0:
        return False

    mid = len(L)//2 # mid point between 0 and len(L)
    if x < L[mid]:
        return rbinsearch(x, L[:mid]) # look at left sublist
    elif x > L[mid]:
        return rbinsearch(x, L[mid+1:]) # look at right sublist
    elif x == L[mid]:
        return True