#
# lab4task2.py - debugging a recursive function
#

# Since one possible cause of infinite recursion is an improperly
# formed recursive call, we check the recursive call in the function
# and notice a typo, which we fix by changing values[:1] to
# values[1:].
#
# Trying num_smaller(6, [8, 5, 7, 4]) now produces the correct result (2)!
#
# However, the call num_smaller(6, [8, 5, 7]) does not work! 
# It still produces infinite recursion.
#
# To diagnose the problem, we add this temporary print statement at
# the start of the function:
#
#     print('starting call for', val, values)
#
# If we now call num_smaller(6, [8, 5, 7]) again, and scroll up to see the
# messages printed before the call crashes, we should see something
# that looks like this:
#
#   ...
#   starting call for 6 []
#   starting call for 6 []
#   starting call for 6 []
#   ...
#
# The problem now is that we're not detecting an empty list, which
# should be a base case but isn't. Adding an additional base case
# fixes the problem.
#
# It's worth noting that we could have gotten by with using the empty
# list as our *only* base case. The original base case wasn't
# strictly necessary, because the combination of the empty-list case
# and the recursive case would still return 1 for cases in which
# values has a length of 1 and its only value is a match for val.
#
# Note also that we have commented out the temporary print statement.
# Please make sure to remove or comment such statements in your own code.
#

def num_smaller(val, values):
    """ returns the number of elements in values that are 
        smaller than val
        parameters:
            val -- an arbitrary value
            values -- a list of 0 or more arbitrary values
    """
    # print('starting call for', val, values)
    if values == []:     # new base case
        return 0
    elif len(values) == 1 and values[0] < val:   # not strictly needed
        return 1
    else:
        num_in_rest = num_smaller(val, values[1:])    # fixed
        if values[0] < val:
            return num_in_rest + 1
        else:
            return num_in_rest