CODEWITHSUNDEEP
pythonlistsortingrecursionpython-3.x
AppliedNumbers
AppliedNumbers

Reputation: 96

Recursively Identifying Sorted Lists

As a recursion practice exercise, I am writing a Python function that recursively identifies if the input list is sorted from least to greatest, real numbers only, and then returns a Boolean value.

My code is:

def det_sorted(listA):
    if len(listA) == 1:
        return(True)
    else:
        if listA[0] <= det_sorted(listA[1:]):
            return(True)
        elif listA[0] > det_sorted(listA[1:]):
            return(False)

This function always returns 'False.' The general question: how do I iterate recursively through the list correctly? My specific question: what have I done wrong here?

Upvotes: 3

Views: 1903

Answers (4)

AppliedNumbers
AppliedNumbers

Reputation: 96

Here is a very explicit script that works.

def det_sorted(listA):
    if len(listA) == 1:
        return(True)
    else:
        if det_sorted(listA[1:]) == True:
            if listA[0] <= listA[1]:
                return(True)
            elif listA[0] > listA[1]:
                return(False)
        else:
            return(False)

Upvotes: 0

Sbbs
Sbbs

Reputation: 1670

Your function doesn't take into consideration the case where listA is empty, which should evaluate as sorted. So the full function should look like this:

def is_sorted(listA):
  if len(listA) == 0 and len(listA) == 1:
      return True
  else:
      return  listA[0] <= listA[1] and is_sorted(listA[1:])

This could be shortened a bit:

def is_sorted(listA):
  if not (listA and listA[1:])
      return True
  return listA[0] <= listA[1] and is_sorted(listA[1:])

Upvotes: 0

Nolen Royalty
Nolen Royalty

Reputation: 18653

@Joran Beasley's answer is correct, but here's another solution to the problem that should be a bit quicker:

def is_sorted(l, prev=None):
    if l:
        if prev is None: return is_sorted(l[1:], l[0])
        else: return l[0] > prev and is_sorted(l[1:], l[0])
    else:
        return True

Upvotes: 2

Joran Beasley
Joran Beasley

Reputation: 114038

you are close , you want to call the recursion for the return

else:
        if listA[0] <= listA[1]:
             return sorted(listA[1:])

or you could combine both statements into the return (and get rid of the else)

return  listA[0] <= listA[1] and sorted(listA[1:])

Upvotes: 5

Related Questions