Recursive Python Simple Function

Question

I'm doing the MIT Intro to CS class to learn python and am stuck on a problem set involving recursive programming(calling a function within itself). The goal is to find a number of occurrences for a given target string. I have the following code and from my logic it seems like it should but I can't figure out why it doesn't! Any help is much appreciated. Thanks.

def countSubStringMatchRecursive(target,key):
    answers = []
    match = target.find(key)

    if match != -1:
        answers.append(match)
        next_target = target[match+1:]
        countSubStringMatchRecursive(next_target,key)

    return len(answers)

So for given arguments:

target1 = 'mjzzmjzzmj'
key1 = 'zz'

print(countSubStringMatchRecursive(target1, key1))

I get 1 instead of the correct answer of two.

This is on Python3 btw.

Please explain exactly how your code fails. Does it crash? Return the wrong data? (Example input/output/expected) — Blorgbeard
– Blorgbeard, Commented Aug 10, 2015 at 1:10
Do you just want the count, or do you want the indices? What about overlapping matches, e.g. 'aba' occurs twice in 'ababa' if you allow for overlaps. — Cyphase
– Cyphase, Commented Aug 10, 2015 at 1:13
See edit. I get a wrong answer. I'm looking for the count here. — MJ49
– MJ49, Commented Aug 10, 2015 at 1:14
You're getting a final result of 1 because you're not returning the answers up through the call chain, so it only returns 0 or 1, depending on whether or not there are any occurrences. — Cyphase
– Cyphase, Commented Aug 10, 2015 at 1:15
answers[] needs to be outside of your method creation. Otherwise, each time it is creating a new one — FirebladeDan
– FirebladeDan, Commented Aug 10, 2015 at 1:16

Cyphase · Accepted Answer · 2015-08-10 01:19:29Z

2

Since you don't need the answers.. you don't need the answers; just a count.

from __future__ import print_function


def countSubStringMatchRecursive(target, key):
    match = target.find(key)

    if match != -1:
        next_target = target[match+1:]
        return 1 + countSubStringMatchRecursive(next_target, key)
    else:
        return 0


print(countSubStringMatchRecursive('asd asd asd', 'sd'))  # 3
print(countSubStringMatchRecursive('ababa', 'ab'))  # 2

This does count overlapping matches; let me know if that's not what you want.

answered Aug 10, 2015 at 1:19

Cyphase

12k3 gold badges33 silver badges33 bronze badges

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

Comments

X.Ceng · Accepted Answer · 2016-12-01 09:49:40Z

0

Cause your variable "answer" is in the body of the function. Hence every time you call the function, it will be reset as "answer=[]"

answers=[]

def countSubStringMatchRecursive(target,key):
    match = target.find(key)

    if match != -1:
        global answers
        answers.append(match)
        next_target = target[match+1:]
        countSubStringMatchRecursive(next_target,key)

    return len(answers)

target1 = 'mjzzmjzzmj'
key1 = 'zz'

print(countSubStringMatchRecursive(target1, key1))

answered Dec 1, 2016 at 9:49

X.Ceng

1

Collectives™ on Stack Overflow

Recursive Python Simple Function

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related