Using python 3 for recursive Boolean check if a list is sorted

here is what I came up with. I designate the default list to 0; first check to see if first item is the last item. if not, should check each item until it reaches the end of the list.

def isSorted(L):
    # Base case
    if len(L) == 1:
        return True

return L[0] <= L[1] and isSorted(L[1:])

This is how I would start. Write a function with the following signature:

function isSorted(currentIndex, collection)

Inside the function, check to see if currentIndex is at the end of the collection. If it is, return true.

Next, check to see if collection[index] and collection[index+1] are sorted correctly.

If they aren't, return false
If they are, return isSorted(currentIndex+1, collection)

Warning: this is a horrible use for recursion

No, the base case will be when you reach the end of the list, in which case you return true.

Otherwise, if the two elements you are looking at are out of order return false.

Otherwise, return the result of a recursive call on the next elements down the list.

I agree with @MStodd: recursion is not the way to solve this problem in Python. For a very long list, Python may overflow its stack! But for short lists it should be okay, and if your teacher gave you this problem, you need to do it this way.

Here is how you should think about this problem. Each recursive call you should do one of three things: 0) return False because you have found that the list is not sorted; 1) return True because you have reached your base case; 2) break the work down and make the remaining problem smaller somehow, until you reach your base case. The base case is the case where the work cannot be broken down any further.

Here is a broad outline:

def recursive_check(lst, i):
    # check at the current position "i" in list
    # if check at current position fails, return False
    # update current position i
    # if i is at the end of the string, and we cannot move it any more, we are done checking; return true
    # else, if i is not at the end of the string yet, return the value returned by a recursive call to this function

For example, here is a function that checks to see if there is a character '@' in the string. It should return True if there is no @ anywhere in the string.

def at_check(s, i):
    if s[i] == '@':
        return False
    i += 1
    if i >= len(s):
        return True
    else:
        return at_check(s, i)

I wrote the above exactly like the outline I gave above. Here is a slightly shorter version that does the same things, but not in exactly the same order.

def at_check(s, i=0):
    if i >= len(s):
        return True
    if s[i] == '@':
        return False
    return at_check(s, i+1)

EDIT: notice that I put i=0 in the arguments to at_check(). This means that the "default" value of i will be 0. The person calling this function can just call at_check(some_string) and not explicitly pass in a 0 for the first call; the default argument will provide that first 0 argument.

The only time we really need to add one to i is when we are recursively calling the function. The part where we add 1 is the important "breaking down the work" part. The part of the string we haven't checked yet is the part after i, and that part gets smaller with each call. I don't know if you have learned about "slicing" yet, but we could use "slicing" to actually make the string get smaller and smaller with each call. Here is a version that works that way; ignore it if you don't know slicing yet.

def at_check(s):
    if s == '':  # empty string
        return True
    if s[-1] == '@':  # is last character '@'?
        return False
    return at_check(s[:-1]) # recursive call with string shortened by 1

In this version, an empty string is the basis case. An empty string does not contain @, so we return True. Then if the last character is @ we can return False; but otherwise we chop off the last character and recursively call the function. Here, we break the work down by literally making the string get shorter and shorter until we are done. But adding 1 to the index variable, and moving the index through the string, would be the same thing.

Study these examples, until you get the idea of using recursion to break down the work and make some progress on each recursive call. Then see if you can figure out how to apply this idea to the problem of finding whether a list is sorted.

Good luck!