# Fruitful Recursion lab

# Worksheet
# implement function grabFirst in 3 ways:

# loop
def grabFirstLoop(listOfNames):
    listFirst = []
    for name in listOfNames:
        listFirst.append(name[0])
    return listFirst
            
# list comprehension (not covered in Fall 2020, but kinda cool to see)
def grabFirstLC(listOfNames):
    return [name[0] for name in listOfNames] 

# recursive
def grabFirstRec(listOfNames):
    if len(listOfNames) < 1:
        return []
    else:
        return [listOfNames[0][0]] + grabFirstRec(listOfNames[1:]) 

def countDivides(num):
    if num <= 1:
        return 0
    else:
        return 1 + countDivides(num/2)
    

# Fruitful Recursion lab coding tasks

def sumUpToCorrect(num):
    '''Returns the sum of all integers from 1 up to and
    including num'''
    if num <= 0:
        return 0
    else:
        return num + sumUpToCorrect(num-1)

def sumBetween(start, end):
    '''Returns the sum of all numbers between start and end, inclusive.
    Assumes that start and end are always non-negative numbers.'''
    if start == end:
        return start
    else:
        return start + sumBetween(start+1,end)
        

def sumOdd(numbers):
    """
    Computes the sum of all the odd integers in the given list of
    numbers, using recursion.
    """
    if len(numbers) == 0:
        return 0
    else:
        first = numbers[0]
        rest = numbers[1:]
        result = sumOdd(rest)
        if first % 2 == 1:
            result += first
        return result

print("Tests for sumOdd:")
print(sumOdd([1, 2, 3, 4]))
print(sumOdd([2, 4, 8]))
print(sumOdd([]))
print(sumOdd([3, 5, 6, 7]))


def mapO(listOfStrings):
    """Returns a list of all the strings with the letter 'o' added
    to the end of each string in the list
    """
    if len(listOfStrings) > 0:
        return [listOfStrings[0]+'o'] + mapO(listOfStrings[1:])
    else:
        return []
        
def exp(base, exponent):
    """Returns the number that is the result of the base to the given exponent
    """
    if exponent < 0:
        return 'This function handles non-negative exponents only'
    if exponent == 0:
        return 1
    else:
        return base*exp(base, exponent-1)

def findMax(numbers):
    """
    Returns the largest number from a list of numbers, using recursion
    and without using the built-in max() function.
    """
    if len(numbers) == 1:
        return numbers[0]
    else:
        first = numbers[0]
        rest = numbers[1:]
        alternate = findMax(rest)
        # figure out which is bigger, the first or the alternate and return that one
        if first > alternate:
            return first
        else:
            return alternate

print("Tests for findMax:")
print(findMax([1, 2, 3]))
print(findMax([2.5, 2.1, 0]))
print(findMax([1, 3, 5, 4, 8, 2, 4, 8, 1]))
print(findMax([100]))

        
def dropRs(listOfStr):
    """Returns a list containing only the strings that did not start with the letter 'r'.
    Any strings that start with 'r' are dropped from the resulting list. 
    
    """
    if len(listOfStr) > 0:
        if listOfStr[0][0].lower() == 'r':
            return dropRs(listOfStr[1:])
        else:
            return [listOfStr[0]] + dropRs(listOfStr[1:])
    else:
        return []
        
def countAndDropRs(listOfStr):
    """ Returns a tuple containing two items:
          1. a list contain only the strings that did not start with the letter r,  and
          2. the number of strings that were dropped from the original list
    """
    if len(listOfStr) > 0:
        if listOfStr[0][0].lower() == 'r':
            newList, count = countAndDropRs(listOfStr[1:])
            return (newList, 1 + count)
        else:
            newList, count = countAndDropRs(listOfStr[1:])
            return ([listOfStr[0]] + newList, count)
    else:
        return ([], 0)
        
def biggestSumLessThan(numbers, limit):
    """
    Returns the largest non-negative number that can be produced by
    adding together some of the numbers in the given list, as long as
    that number is strictly less than the given limit. So for example, if
    the numbers list is [1, 3, 5] and the limit is 8, the result will be
    6 (1 + 5) since 3 + 5 would be too large, and 1 + 3 is smaller than 1
    + 5. Returns 0 if the list of numbers is empty, or if the given limit
    is less than or equal to 0.
    """
    if len(numbers) == 0 or limit <= 0:
        return 0 # no numbers so we default to zero
    else:
        first = numbers[0]
        rest = numbers[1:]
        if first >= limit:
            return biggestSumLessThan(rest, limit)
        else:
            optionOne = first + biggestSumLessThan(rest, limit - first)
            optionTwo = biggestSumLessThan(rest, limit)
            return max(optionOne, optionTwo)

print("Tests for biggestSumLessThan:")
print(biggestSumLessThan([2, 4, 6, 8], 15))
print(biggestSumLessThan([3, 3, 3, 4], 9))
print(biggestSumLessThan([15, 4, 4, 4, 5, 5, 5], 19))
print(biggestSumLessThan([1.2, 0.8, 0.4, 0.5, 0.3], 2.5))