def moveDiscs(start, tmp, end, discs):
    if discs == 1:
        print("Move one disc from", start, "to", end)
        return 1
    else:
        moves = 0
        moves += moveDiscs(start, end, tmp, discs-1)
        moves += moveDiscs(start, tmp, end, 1)
        moves += moveDiscs(tmp, start, end, discs-1)
        return moves
    
result = moveDiscs("left", "middle", "right", 4)
print(result)

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

print(recLinearSearch([1,5,2,3,9,3,12], 5))
print(recLinearSearch([1,5,2,3,9,3,12], 4))



def recBinarySearch(lst, target):
    if lst == []:
        return False
    else:
        midIndex = len(lst) // 2
        if lst[midIndex] == target:
            return True
        elif target < lst[midIndex]:
            return recBinarySearch(lst[0:midIndex], target)
        else: # target was bigger than the middle element
            return recBinarySearch(lst[midIndex + 1:], target)

print(recBinarySearch([1,2,3,4,6,8,10], 7))
print(recBinarySearch([1,2,3,4,6,8,10], 3))