A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 5 years ago

Base case for recursion? I understand the concept of recursion, but for Problem Set 3 problem 1 part b I'm having a hard time coming up with a base case. Any hints? Thanks.

  • This Question is Closed
  1. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    how about "if the keystring is NOT in the targetstring/current section of the targetstring, return 0/something else that lets you stop calculating"

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

    I have something that works, but I can't figure out how to print out a number of instances. I can just print out 'one instance' per time the key is found. How can I print out the actual number of instances? def countSubStringMatchRecursive(target, key): index = 0 target_length = len(target) if find(target[index:target_length], key) == -1: # test to see if value is returned return 0 else: position = find(target[index:target_length], key) index = position + 1 print "one instance" return countSubStringMatchRecursive(target[index: target_length], key) I tried to return a counter variable that increments, but when i print it it always stays at 0. Thanks in advance. def countSubStringMatchRecursive(target, key): index = 0 target_length = len(target) counter = 0 if find(target[index:target_length], key) == -1: # test to see if value is returned print counter return 0 else: position = find(target[index:target_length], key) index = position + 1 counter += 1 print "one instance" return countSubStringMatchRecursive(target[index: target_length], key) and counter

  3. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I think your problem lies in your IF statement. I think you need to use a WHILE loop...otherwise your code will choose one of your two paths, execute, then end. The while loop will look until your counter max is achieved.

  4. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    You can also try a FOR loop, as I did in my code. It works, but you have to have the right conditions. Make sure your conditions can be met, and make sure that it will iterate or recur for all instances of your key.

  5. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I'm honestly still not that happy with my solutions to this problem set, so someone should jump in if I start talking nonsense. Basically, for this problem I think you need another parameter besides target and key. It would be a 0 int or an empty or nearly-empty list, and it would get iterated at each recursion. The pseudocode would look like: recursionfunction(target,key, counter): if the keystring is not in the targetstring: return the counter else: add one to the counter location = where it was found return the result of the recursionfunction with a shortened targetstring and the current key and counter

  6. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Try this. No extra counting parameter needed. def countSubStringMatchRecursive(target, key): found_at = target.find(key) if found_at >=0: return 1+ countSubStringMatchRecursive(target[found_at+1:], key) else: return 0 # not found

  7. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yeah, that's better. Thanks!

  8. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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.