Python 3.3: Recursive version of a function

Question

def abc(s):
    filter = [i for i in s.lower() if i in 'abcdefghijklmnopqrstuvwxyz']
    for i in range(len(filter) - 1):
        if filter[i] > filter[i+1]:
            return print(s, "is not abcdearian")
    return print(s,  "is abcdearian")


while True:
    try:
        s = input("String? ")
abc(s)

I'am having trouble making a recursive version of abc(s). Any ideas?

Answer 1

Non-recursive solution:

def issorted(L):
    return all(x <= y for x, y in zip(L, L[1:]))

To make a recursive function you should find a way to split the problem into smaller and/or simpler subproblems that could be solve the same way:

#!/usr/bin/env python3
from string import ascii_lowercase

def abcdearian(s):
    return issorted_recursive([c for c in s.lower() if c in ascii_lowercase])

def issorted_recursive(L):
    return L[0] <= L[1] and issorted_recursive(L[1:]) if len(L) > 1 else True

Here issorted_recursive() is a recursive function. The base case is len(L) <= 1 (a list with zero or one element is always sorted so return True in this case). In the recursive case (len(L) > 1) the list L is considered sorted if the first item is in the sorted order (L[0] <= L[1]) and the rest of the list (L[1:]) is also sorted. Each time the function receives smaller and smaller input until out of order element is found (L[0] > L[1]) or the base case is encountered and the function finishes.

Example

while True:
    s = input("String? ")
    if not s:
        break
    print("{} is {}abcdearian".format(s, "" if abcdearian(s) else "not "))

Input

    abc
    bac

Output

String? abc is abcdearian
String? bac is not abcdearian
String?