"""
Learning Goals:
 - Trace over recursive functions that use multiple recursive calls with Towers of Hanoi
 - Recognize linear search on lists and in recursive contexts
 - Use binary search when reading and writing code to search for items in sorted lists
"""


def moveDiscs(start, end, tmp, numDiscs):
    if numDiscs == 1:
        print("Move " + str(numDiscs) + " from " + start + " to " + end)
        return 1
    else:
        moves = 0
        moves += moveDiscs(start, tmp, end, numDiscs-1)
        moves += moveDiscs(start, end, tmp, 1)
        moves += moveDiscs(tmp, end, start, numDiscs-1)
        return moves

print(moveDiscs("left", "right", "middle", 4))

###

def linearSearch(lst, target):
    for item in lst:
        if item == target:
            return True
    return False

def linearSearch(lst, target):
    print(lst)
    if len(lst) == 0:
        return False
    elif lst[0] == target:
        return True
    else:
        return linearSearch(lst[1:], target)

print(linearSearch([54, 23, 12, 7, 8, 43], 12))

###

def binarySearch(lst, target):
    print(lst)
    if len(lst) == 0:
        return False
    mid = len(lst) // 2
    if lst[mid] == target:
        return True
    elif target < lst[mid]:
        return binarySearch(lst[:mid], target)
    else: # lst[mid] < target
        return binarySearch(lst[mid+1:], target)

print(binarySearch([7, 8, 12, 23, 43, 54], 21))