def moveDiscs(start, tmp, end, discs):
    if discs == 1:
        print("Move one disc from ", start, "to", end)
        return 1
    else:
        numMoves = 0
        numMoves = numMoves + moveDiscs(start, end, tmp, discs-1) # x
        numMoves = numMoves + moveDiscs(start, tmp, end, 1) # 1
        numMoves = numMoves + moveDiscs(tmp, start, end, discs-1) # x
        return numMoves

print("Result", moveDiscs("left", "middle", "right", 4))
    
###
    
def linearSearch(lst, target):
    if lst == []:
        return False
    elif lst[0] == target:
        return True
    else:
        return linearSearch(lst[1:], target)

print(linearSearch([4, 1, 23, 17, 5, 8], 5))
print(linearSearch([4, 1, 23, 17, 5, 8], 9))

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

print(binarySearch([1, 5, 7, 9, 22, 34, 50], 21))
print(binarySearch([1, 5, 7, 9, 22, 34, 50], 34))