Keeping count in recursive function

Question

I'm trying to figure out how to write a recursive function (with only one parameter) that returns the number of times the substring “ou” appears in the string. Where I'm confused at is that I'm not allowed to use any built-in string functions other than len, or the string operators [] and [:] for indexing and splicing. So I can't use the find built-in find function

I remember seeing something like this, but it uses two parameters and it also uses the find() method

def count_it(target, key):
  index = target.find(key)
  if index >= 0:
    return 1 + count_it(target[index+len(key):], key)
  else:
    return 0

What type can the argument be? Are you allowed to pass in a tuple? — Mark Byers
– Mark Byers, Commented Nov 1, 2011 at 20:22

Mark Byers · Accepted Answer · 2011-11-01 20:30:16Z

2

Very inefficient, but should work:

def count_it(target):
    if len(target) < 2:
        return 0
    else:
        return (target[:2] == 'ou') + count_it(target[1:])

See it working online: ideone

It's basically the same idea as the code you posted, except that it moves only one character at a time through the string instead of using find to jump ahead to the next match.

edited Nov 1, 2011 at 20:30

answered Nov 1, 2011 at 20:24

Mark Byers

844k202 gold badges1.6k silver badges1.5k bronze badges

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

2 Comments

Will S Over a year ago

It works!! I'm only a beginner, but why would you say that it's inefficient?

Mark Byers Over a year ago

@Will S: The main problem is that x[1:] requires copying the entire string (apart from the first character). This gives an O(n*n) complexity.

Óscar López · Accepted Answer · 2011-11-01 20:42:41Z

0

Try this, it works for the general case (any value of key, not only 'ou'):

def count_it(target, key):
    if len(target) < len(key):
        return 0
    found = True
    for i in xrange(len(key)):
        if target[i] != key[i]:
            found = False
            break
    if found:
        return 1 + count_it(target[len(key):], key)
    else:
        return count_it(target[1:], key)

answered Nov 1, 2011 at 20:42

Óscar López

237k38 gold badges321 silver badges391 bronze badges

Collectives™ on Stack Overflow

Keeping count in recursive function

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related