Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

tmd197 Group Title

I am working on ps3 and they're asking for two functions to iteratively and recursively count the number of matches of the key in the target. This seems too obvious for part a: def countSubStringMatch(target,key): print target.count(key) is this correct? and then secondly, I don't have any idea how to do it recursively. I tried to write a recursive function that would tell me exactly where the key is hiding in the target but it's not working:

  • 2 years ago
  • 2 years ago

  • This Question is Closed
  1. tmd197 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    def countSubStringMatchRecursive(target,key): y = find(target,key) print y while y!= -1: countSubStringMatchRecursive(target[y+1:len(target)],key)

    • 2 years ago
  2. JulieNewbie Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Yes, the iterative function is that easy. I've been stuck on exactly the same problem with making it recursive. I actually spent an embarrassing amount of time weeding through ancient posts in this group, and I dug up the 4 codes on the link below. And just for kicks, I added your code, too. I modified the whole thing so that each one will print out some results so I can figure out what the heck they each did. I'm sure several other study groupies will recognize their own code: http://dpaste.com/hold/612083/ You will notice that the second one doesn't give the same results as #1, 3, and 4. Function 5 is your code (which seems to have an infinite loop in it, although it reports the correct answer as the second value). Because I don't quite understand how to make this problem recursive, I can't tell you why any of these 5 examples do or don't work. I'm kinda hung up on "from string import *" right now. Something else helpful I dug up in ancient questions was this: The assignment is to write functions for how many times the key occurs in a target. We're not asked to report the indices of those matches (which I spend a few days trying and failing to do). Please, if you figure it out, post it!

    • 2 years ago
  3. JulieNewbie Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    In my dpaste post, most everyone did this: return 1 + countSubStringMatchRecursive(target[nextindex:], key) I don't understand why they added one to the re-call of their functions. And BTW, this seems to be what tmd197's function is missing.

    • 2 years ago
  4. carlsmith Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    Julie, do you know what people mean by basecase?

    • 2 years ago
  5. JulieNewbie Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    the base case does not make a recursive call.

    • 2 years ago
  6. carlsmith Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    That's right; it's what stops the recursion. If you have a function that calls itself: def f(): return f() When you call it, `f()`, the interpretor will stop executing the code around the function call and start executing the function definition. Which requires the interpretor to stop executing that definition, create another instance of `f`, then execute that, and so on, and so on, You'll just get loads of instances of the function, but they'll never return anything. So it'll be infinite recursion all the way. You need a basecase in the definition to stop it at some point. In order for that to happen, the argument passed will need to change with each new instance...

    • 2 years ago
  7. carlsmith Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    Take the following function: def f(n): if n == 2: return 2 else: return n * f(n - 1) Have a look at it, I'll try and explain...

    • 2 years ago
  8. JulieNewbie Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Isn't that what this does: countSubStringMatchRecursive4(target[target.find(key)+1:] I get adding one inside the index. The function that worked in my dpaste was: countSubStringMatchRecursive4(target[target.find(key)+1:] + 1 Why add one to the whole thing? Wouldn't that give you the index + 1, which would then be one more than the correct answer?

    • 2 years ago
  9. carlsmith Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    If I call it, passing, lets say 3: f(3) because 3 is not equal to two, the else part will be executed. That'll create a new instance of `f`, passing n - 1, which would be 2. This will also prevent the first instance from returning anything for now. The new instance, passed 2, will return 2, because that's what it does whenever it's passed 2. It returns 2 to the first instance, which is still waiting to know what f(n -1) is. It is 2, so the first instance returns n * 2, or 3 * 2, which is 6 of course. If I pass a bigger number, say 100, it'll just take longer, as it'll spawn a long chain of instances of the function `f`, each waiting for the one that gets passed 2, to return 2, allowing it to reel back in, garbage collecting each instance of the function as it returns, so that, eventually, the first one called, can return 100 * 99 * 98 * 97 ... 3 * 2

    • 2 years ago
  10. carlsmith Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    f(4) return 4 * f(3) f(3) return 3 * f(2) f(2) return 2

    • 2 years ago
  11. carlsmith Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    4 * 3 * 2

    • 2 years ago
  12. carlsmith Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    I can't read the code you posted on dpaste, the links dead.

    • 2 years ago
  13. JulieNewbie Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Thank you, carlsmith. You are a very patient man! Yes, I understand why you want to add one to it. But it seems like the successful codes in my dpaste added one to the index AND one to the whole thing. That seems redundant.

    • 2 years ago
  14. carlsmith Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    Ah, see, I can't read the code. I'm not sure what it's meant to do. This line... countSubStringMatchRecursive4(target[target.find(key)+1:] should throw a syntax error, as should... countSubStringMatchRecursive4(target[target.find(key)+1:] + 1 They both, lack a closing paren.

    • 2 years ago
  15. carlsmith Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    Sorry, Julie, you'll have to post the code again mate.

    • 2 years ago
  16. JulieNewbie Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Hmmm... don't know where it went. Let's try that again: http://dpaste.com/hold/612100/

    • 2 years ago
  17. carlsmith Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    I'll have a look now.

    • 2 years ago
  18. carlsmith Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    Which one works?

    • 2 years ago
  19. JulieNewbie Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    #1, #3, and #4

    • 2 years ago
  20. carlsmith Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    k

    • 2 years ago
  21. carlsmith Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    The third one has a one one the end, because it doesn't have it at the front of the expression. return countSubStringMatchRecursive4(target[target.find(key)+1:],key)+1 return 1 + countSubStringMatchRecursive4(target[target.find(key)+1:],key) The 1 represents the match that must have been found if the else block is being executed.

    • 2 years ago
  22. carlsmith Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    It's pretty ugly code to be honest. You should use nicer names for things, don't listen to the geeks. def count_matches(string, substring): if string.find(substring) == -1: return 0 else: return 1 + count_matches(string[ string.find(substring)+1: ], substring) Try and keep it clean and tidy.

    • 2 years ago
  23. JulieNewbie Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Shame I can only give you one medal :*

    • 2 years ago
  24. carlsmith Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    Thank you. Have a go at it, but if you want to learn recursion, which, to be honest, isn't that useful very often, you'd still be better of starting with numbers, little ones. Iterating around the place at the same time, just make's it too confusing. My function above will take the number of cards in a deck and return the odds to one of the deck being shuffled and ending up in some predetermined order. For a regular deck, the odds are simply 52*51*50...4*3*2. That's all it does, but it shows how recursion works without many moving parts.

    • 2 years ago
  25. carlsmith Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    Let me know if you're still stuck. I skipped recursion when I first started and came back to it. It's painful at first.

    • 2 years ago
  26. walkerp1 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Recursion is a neat concept, but it isn't suitable for really deep applications. A quick test shows: def recurse_check(calls): calls[0] += 1 recurse_check(calls) calls=[0] try: recurse_check(calls) except RuntimeError: print 'Number of calls:',calls[0] Output: Number of calls: 999

    • 2 years ago
  27. bwCA Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    of all the things they could have taught in an intro class, i wonder why they decided to include recursion?

    • 2 years ago
  28. JulieNewbie Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I'm glad to hear it isn't a simple concept. I find iteration WAY more intuitive. Oh, and sorry to tmd197 for hijacking your question ;) I'm hoping all this chatter was helpful for you, too.

    • 2 years ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.