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

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

def recursiveLinearSearch(lst, target):
    print(lst)
    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"))

print("---")

def binarySearch(lst, target):
    print(lst)
    if lst == []:
        return False
    else:
        midIndex = len(lst) // 2
        if lst[midIndex] == target:
            return True
        elif target < lst[midIndex]:
            return binarySearch(lst[:midIndex], target)
        else: # target > lst[midIndex]
            return binarySearch(lst[midIndex+1:], target)
print(binarySearch([2, 5, 10, 20, 42, 56, 67, 76, 89, 95], 95))