# Finds the nth triangle number recursively.
# Requires that n >= 0
def tri(n):

    # This is our base case.
    if n == 0:
        return 0

    # Otherwise, find tri(n-1) and just add n to it.
    return n + tri(n-1)

# Finds the nth Harmonic number
# Requires that n >= 0
def harmonic(n):

    # This is our base case.
    if n == 0:
        return 0

    # Similar to triangle numbers but add reciprocal to recursive call.
    return 1.0/n + harmonic(n-1)

def proddigits(n):

    # One digit left.
    if n < 10:
        return n

    # Peel off the last digits via mod, and multiply that by the product
    # of the rest of the digits.
    return (n%10)*proddigits(n//10)

def towercost(n):

    # No work for tower size 0.
    if n == 0:
        return 0

    # The cost of moving the bottom disk is n. For the rest of the disks, we solve the
    # towers problem on them twice, so call the function once and multiply that cost by 2.
    return 2*towercost(n-1) + n

def binsearch(arr,low,high,val):

    # Not found.
    if low > high:
        return -1

    # Middle index for search.
    mid = (low+high)//2

    # We're looking for something smaller, go left.
    if val < arr[mid]:
        return binsearch(arr, low, mid-1, val)

    # We're looking for something larger, go right.
    elif val > arr[mid]:
        return binsearch(arr, mid+1, high, val)

    # We found it; we edit by returning the index, mid.
    else:
        return mid

# Tests
print(tri(40))
print(harmonic(10))
print(proddigits(8234512))
print(towercost(5))

# Binary search.
mynums = [2, 4, 5, 12, 22, 40, 54, 100, 345, 12345]
for i in range(100000):
    x = binsearch(mynums,0,len(mynums)-1, i)

    if x != -1:
        print("Found",i,"in index",x)