CODEWITHSUNDEEP
pythonsortingrecursion
user2559679
user2559679

Reputation: 89

Recursive function with alphabetical order

I want to define a recursive function that passes a str and returns a bool telling whether or not the characters in the parameter are in alphabetical order.

Like if I defined said sortfunc('abcdefg') it would return True; and sortfunc('banana') would return False.

How would I approach this? This is what I have so far... but I'm sort of stuck. I understand the concept of recursion but I don't know how to implement it.

def sortfunc(s):
    if s == '':
        return False
    else:
        return True if s[0] < s[1:] else False

Upvotes: 0

Views: 3563

Answers (3)

Michael0x2a
Michael0x2a

Reputation: 64188

Here's one possible method:

def is_sorted(s):
    if len(s) == 1:
        return True               # Base case
    elif s[0] <= s[1]:
        return is_sorted(s[1:])   # Recursive case
    else:
        return False              # Base case

Explanation:

So, whenever, we want to write a recursive function, we always need to think about the following:

  1. How can I break the problem down into smaller steps?
  2. What is the base case? (when I can stop the recursion?)
  3. What is the recursive case? (when do I need to keep going?)

To me, the first step is always the trickiest one -- breaking the problem down. Usually, once we figure out this step, the rest falls into place.

There are usually many different ways to break a problem down, and to a certain extent, which one you pick is a bit arbitrary. In this case, I chose to break the problem down by repeatedly comparing the first two characters in the string.

If the two characters are in order, then I repeat the process, except I remove the first character. If I have only one character left in my string, or if the first two characters are out of order, I know that I can stop and return True or False respectively.

For example, if we visualize calling is_sorted('abcd'), it would look something like this:

call is_sorted('abcd')
    'a' is less then 'b'
    call is_sorted('bcd')
        'b' is less then 'c'
        call is_sorted('cd')
            'c' is less then 'd'
            call is_sorted('d')
                only one character left, return True
            return True
        return True
    return True

In contrast, if we tried calling is_sorted('azbc'), it would look something like this:

call is_sorted('azbc')
    'a' is less then 'z'
    call is_sorted('zbc')
        'z' is NOT less than 'b', return False
    return False

So then, here are the answers to the three steps:

  1. How can I break the problem down into smaller steps?
    Keep comparing the first two characters

  2. What is the base case? (when I can stop the recursion?)
    Either when the two characters are out of order, or if I have only one character left

  3. What is the recursive case? (when do I need to keep going?)
    If I have two or more characters left in my string.

Notice that the recursive case always requires a "leap of faith" -- you have to trust that calling the is_sorted method will accurately tell you if the rest of the string (besides the first two characters) is correctly sorted or not. It's a bit of an odd feeling -- it feels like we never explicitly told the code how to determine if the string is coded or not, or passed in any information, but it does so anyways!

However, that's part of the beauty of recursion: so long as we correctly define the base case(s) and recursive case(s), it'll magically work.

Upvotes: 3

Manesh M
Manesh M

Reputation: 43

Without less programming logic!

-> Split the string to an array and send this array to function

-> we can easily compare values by converting them to respective ascii values

sortfunc(str) {

for(int i=0;i<str.length;i++){

if ( (int) str[i] >(int) str[i+1] ) {
result = true
}
else
result = false;

return result;
}

Upvotes: 0

thefourtheye
thefourtheye

Reputation: 239573

In your attempt you are missing the recursion part. Please check the following implementation.

def sortfunc(current_string, previous_character = ""):
    if current_string == "":
        return True         # Base condition
    if previous_character and previous_character > current_string[0]:
        return False        # Failure case
    return sortfunc(current_string[1:], current_string[0])  # Recursion

If you want to know how to do this without recursion,

def sortfunc(current_string):
    return "".join(sorted(current_string)) == current_string

Sample runs:

print sortfunc('abcdefg')   # True
print sortfunc('banana')    # False

Upvotes: 1

Related Questions