def moveDiscs(start, temp, end, numDiscs):
    if numDiscs == 1:
        print("Move 1 disc from", start, "to", end)
    else:
        # Move all but one from start to temp
        moveDiscs(start, end, temp, numDiscs-1)
        print("Move 1 disc from", start, "to", end)
        # Move all but one from temp to end
        moveDiscs(temp, start, end, numDiscs-1)
    
moveDiscs("left", "middle", "right", 4)

###

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

print(recursiveLinearSearch(["dog", "cat", "rabbit", "mouse"], "rabbit"))
print(recursiveLinearSearch(["dog", "cat", "rabbit", "mouse"], "horse"))

###

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

print(binarySearch([2, 5, 10, 20, 42, 56, 67, 76, 89, 95], 45))