Andrew Andrew - 1 year ago 88
Python Question

contradictory outputs in simple recursive function

Note: Goal of the function is to remove duplicate(repeated) characters.

now for the same given recursive function, different output pops out for different argument:

def rd(x):
if x[0]==x[-1]:
return x
elif x[0]==x[1]:
return rd(x[1: ])
return x[0]+rd(x[1: ])
print("Enter a sentence")
print("simplified: "+rd(r))

This functions works well for the argument only if the duplicate character is within the starting first six characters of the string like given below:

r=abcdeeeeeeefghijk or if r=abcdeffffffghijk

but if the duplicate character is after the first six character then the output is same as the input,i.e, output=input.
that means with the given below value of "r", the function doesn't work eg:

if r=abcdefggggggggghijk (repeating characters are after the first six characters)

somebody plz help me with this

Answer Source

The reason you function don't work properly is you first if x[0]==x[-1], there you check the first and last character of the substring of the moment, but that leave pass many possibility like affffffa or asdkkkkkk for instance, let see why:

example 1: 'affffffa'

here is obvious right?

example 2: 'asdkkkkkk'

here we go for case 3 of your function, and then again


and when we are in 'kkkkkk' it stop because the first and last are the same

example 3: 'asdfhhhhf'

here is the same as example 2, in the recursion chain we arrive to fhhhhf and here the first and last are the same so it leave untouched

How to fix it?, simple, as other have show already, check for the length of the string first

def rd(x):
    if len(x)<2: #if my string is 1 or less character long leave it untouched 
        return x
    elif x[0]==x[1]:
        return rd(x[1: ])
        return x[0]+rd(x[1: ])

here is alternative and iterative way of doing the same: you can use the unique_justseen recipe from itertools recipes

from itertools import groupby
from operator import itemgetter

def unique_justseen(iterable, key=None):
    "List unique elements, preserving order. Remember only the element just seen."
    # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B
    # unique_justseen('ABBCcAD', str.lower) --> A B C A D
    return map(next, map(itemgetter(1), groupby(iterable, key)))

def clean(text):
    return "".join(unique_justseen(text)


>>> clean("abcdefggggggggghijk")
>>> clean("abcdefghijkkkkkkkk")
>>> clean("abcdeffffffghijk")

and if you don't want to import anything, here is another way

def clean(text):
    for c in text:
        if c!=last:
            last = c
            result += c
    return result
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download