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? 

Answer 2

The way the accepted answer was originally written, it seemed to be overly complex. I've submitted an edit that hopefully fixes that. But by the time I realized that, I had already written the below answer and explanation. Keeping it, in case the explanation is useful to someone:

def abc(s):
    filtered = [i for i in s.lower() if i in 'abcdefghijklmnopqrstuvwxyz']
    optionalNotString = ('' if _abc(filtered) else ' not')
    print( '{0} is{1} abcdearian'.format( repr(s), optionalNotString ) )

# Recursively process the "rest" (remainder) of the string.
# At each step, examine the first two characters.
def _abc(rest):
    if len(rest) < 2:
        # We've successfully compared all successive pairs, so return True.
        return True
    if (rest[0] > rest[1]):
        return False
    return _abc(rest[1:])

In use (the most important cases to test, including too-short strings, and detecting a False condition at the end of string 'acb', as well as at start of string 'bac'. I had a bug the first way I wrote it, which failed to catch 'bac' as False!):

abc( '' )
abc( 'a' )
abc( 'ac' )
abc( 'abc' )
abc( 'acb' )
abc( 'bac' )

Output:

'' is abcdearian
'a' is abcdearian
'ac' is abcdearian
'abc' is abcdearian
'acb' is not abcdearian
'bac' is not abcdearian

Explanation:

1. The filtering only needs to be done once, so do it in the main "abc" function, not in the recursive "_abc" function.

2. At each step, the algorithm needs to look at two adjacent characters. In each call to "_abc", these will be the first two characters.

3. "_abc" needs to handle two cases:

   • Case 1: The string is too short to perform a comparison. E.g. '' or 'a'. Such strings satisfy the abcderian criterion, so return True.

   • Case 2: The string is at least two characters. Perform the abcderian calculation of the first two. If that fails, the answer is False. Otherwise, recurse with all but the first character.

4. "repr(s)" is an easy way to get "s" to print with its surrounding quotes.

5. "optionalNotString ": The desired answer string in the True/False cases only differs by the presence/absence of ' not'. So use "if .. else .." expression, to control whether ' not' is include in the formatted output. When not wanted, substitute the empty string ''.

Answer 3

Try this code, it's equivalent to the one posted in the question, but written in a recursive style:

from string import ascii_lowercase

def abc(s):
    f = [c for c in s.lower() if c in ascii_lowercase]
    if aux(f, 0):
        return s + " is abcdearian"
    else:
        return s + " is not abcdearian"

def aux(s, i):
    if i >= len(s)-1:
        return True
    elif s[i] > s[i+1]:
        return False
    else:
        return aux(s, i+1)

Use it like this:

while True:
    s = input("String? ")
    if not s:
        break
    print(abc(s))

Notice that I split the problem in two: first the, "main" function abc() takes care of filtering the string, calling the aux procedure with correct initial values and returning the result string at the end (alternatively: you could have returned a boolean, creating the result string elsewhere.)

The real work is done in the helper aux function, which recursively traverses the string checking if the "abcdearian" condition is true for all pairs of consecutive characters in the string. The way aux iterates over the string is efficient (putting aside the fact that we're using recursion), because it never creates additional intermediate strings with s[1:]. It's also an example of a tail-recursive algorithm, and it closely mirrors the structure of the iterative solution.