def moveDiscs(start, temp, end, numDiscs):
    print("Call:", numDiscs, start, end)
    if numDiscs == 1:
        print("Move from", start, "to", end)
    else:
        # move all but one from start to temp
        moveDiscs(start, end, temp, numDiscs - 1)
        # move one from start to end
        print("Move 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 len(lst) == 0:
        return False
    else:
        # len(lst) == 5 - 0, 1, 2, 3, 4 -> 2
        # len(lst) == 4 - 0, 1, 2, 3 -> 2
        middleIndex = len(lst) // 2
        if lst[middleIndex] == target:
            return True
        elif lst[middleIndex] > target:
            return binarySearch(lst[:middleIndex], target)
        else: # lst[middleIndex] < target:
            return binarySearch(lst[middleIndex+1:], target)

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