Keeping the initial value of a variable in recursive function

Question

I am writing a recursive function that will take two strings sub and string. I have to find out if sub is a substring of string.

A recursive function is a strict requirement which can't be removed.

This is what I have tried, but its broken:

def is_substring(sub,string):
    if sub=="":
        return True
    if string=="":
        return False
    if sub[0]==string[0]:
        return is_substring(sub[1:],string[1:])
    if sub[0]!=string[0]:
        return is_substring(sub,string[1:])

It returns True instead of False when:

sub='misip'
string='mississippi'

Do not post a link to an image. Post the code here, as text. — Daniel Roseman
– Daniel Roseman, Commented Dec 19, 2016 at 13:45
Please see Why may I not upload images of code on SO when asking a question?. Hyperlinks can be used to enhance your question, but the core info must be posted in the question itself. Questions that need external links to make sense are not acceptable on SO. — PM 2Ring
– PM 2Ring, Commented Dec 19, 2016 at 13:47
there was a long question before that so i thought showing that might help you, but i wont do that anymore, thanks for the feedback — Ahmet Dara VEFA
– Ahmet Dara VEFA, Commented Dec 19, 2016 at 13:50

PM 2Ring · Accepted Answer · 2016-12-20 07:14:57Z

2

One way to preserve the initial value of an argument to a recursive function is to use an additional keyword argument. It's conventional to give this argument a default value of None so callers of the function don't need to initialize this argument, but when the function calls itself recursively it gets set appropriately, when required.

For example:

def is_substring(sub, string, oldsub=None):
    if sub == "":
        return True
    if string == "":
        return False

    if oldsub is None:
        oldsub = sub

    if sub[0] == string[0]:
        return is_substring(sub[1:], string[1:], oldsub)
    else:
        return is_substring(oldsub, string[1:], oldsub)

Another way to preserve the value is to create a closure by defining the recursive function inside a wrapper function, like this:

def is_substring(sub, string):
    oldsub = sub
    def is_substringR(sub, string):
        if sub == "":
            return True
        if string == "":
            return False

        if oldsub is None:
            oldsub = sub

        if sub[0] == string[0]:
            return is_substringR(sub[1:], string[1:])
        else:
            return is_substringR(oldsub, string[1:])

    return is_substringR(sub, string)

This function implements the same algorithm as the earlier version. And I'm pretty sure that's the algorithm you're trying to implement with your code. Unfortunately, this algorithm doesn't find substrings correctly.

So here's a recursive is_substring that does work correctly, but it doesn't need to preserve old argument values.

def is_substring(sub, string):
    if sub == "":
        return True
    if string == "":
        return False

    if string.startswith(sub):
        return True
    else:
        return is_substring(sub, string[1:])

# some tests

data = (
    ('misip', 'mississippi'),
    ('tle', 'cattle'),
)

for sub, target in data:
    print('{!r} {!r} {}'.format(sub, target, is_substring(sub, target)))

output

'misip' 'mississippi' False
'tle' 'cattle' True

If you don't want to use the .startswith method, you can use slicing instead:

def is_substring(sub, string):
    if sub == "":
        return True
    if string == "":
        return False

    if sub == string[:len(sub)]:
        return True
    else:
        return is_substring(sub, string[1:])

As I said in the comments, the usual way to do a substring test is to use the in operator, which calls the string's .__contains__ method.

sub in string

edited Dec 20, 2016 at 7:14

answered Dec 19, 2016 at 14:36

PM 2Ring

55.6k6 gold badges96 silver badges203 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ahmet Dara VEFA Over a year ago

thank you for the awesome answers, i was trying to do it without using the in and len operators, thank you again, much appreciated.

PM 2Ring Over a year ago

@AhmetDaraVEFA No worries. FWIW, I tried a bunch of variations, trying to find a purely recursive version that tests character by character, but the logic was getting ridiculously complicated, and I still couldn't get it to work correctly in all cases. So I ended up ditching that frustrating exercise and going with the compromise versions using string.startswith(sub) and sub == string[:len(sub)]. :)

iFlo · Accepted Answer · 2016-12-19 13:40:22Z

1

You could add a parameter of you function that never change something like :

def recur(completeString, string ) :
    if string :
        print string
        recur(completeString, string[:-1])
    else :
         print "Nothing left from '{}'".format(completeString)

recur("hello", "hello")

This will output :

hello
hell
hel
he
h
Nothing left from 'hello'

answered Dec 19, 2016 at 13:40

iFlo

1,49411 silver badges21 bronze badges

1 Comment

Ahmet Dara VEFA Over a year ago

this might work but i have to look into it, thank you

Prune · Accepted Answer · 2016-12-19 20:55:53Z

The problem is that your initial call and your later calls have slightly different logic. On failure, your initial call can simply advance to the next character in string; your later calls have to start over from the beginning of sub.

I suggest two functions for this: a wrapper function to make the first comparison and preserve the given interface (or can you change it?), and a second that will look for a continuous match to the end.

Here's a possible solution with tracing print statements inserted (and commented out).

def match_all(sub, string):
    # print "ENTER ALL", sub, string
    if sub == "":
        # print "ALL empty sub; success"
        return True
    if string == "":
        # print "ALL empty str; fail"
        return False
    if sub[0] == string[0]:
        # print "ALL head match: recur"
        return match_all(sub[1:],string[1:])
    else:
        # print "ALL head diff: fail"
        return False

def is_substring(sub,string):
    # print "ENTER TOP", sub, string
    if sub == "":
        # print "empty sub; success"
        return True
    if string == "":
        # print "empty str; fail"
        return False
    if sub[0] == string[0]:
        # print "head match: recur"
        if match_all(sub[1:],string[1:]):
            return True
    # print "head diff: recur"
    return is_substring(sub,string[1:])

print is_substring("misip", "mississippi")
# print "------------"
print is_substring("sip", "mississippi")

Note that logic change: the main function looks for immediate results, but still continues if it finds no such resolution. The support function looks only for an immediate match at this string position.

Collectives™ on Stack Overflow

Keeping the initial value of a variable in recursive function

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related