Question

In problem set 3, I'm having a little trouble getting the recursive program I've written to work correctly. I can watch it in debug mode using the Python IDLE, and it acts recursivly, but how do you get it to count how many recurssions it's gone through. I know I'm thinking iteratively, and that's probably the wrong way to go about it, but I can't quite wrap my head around it I guess. Here's a link to my functions for ps3a; http://codepad.org/xXXxPgxb In problem set 3, I'm having a little trouble getting the recursive program I've written to work correctly. I can watch it in debug mode using the Python IDLE, and it acts recursivly, but how do you get it to count how many recurssions it's gone through. I know I'm thinking iteratively, and that's probably the wrong way to go about it, but I can't quite wrap my head around it I guess. Here's a link to my functions for ps3a; http://codepad.org/xXXxPgxb @MIT 6.00 Intro Co…

Answer 1

First, some comments about the iterative version:
1. Never compare a boolean variable to True/False.
2. Why do you add 1 to the result of find?
3. Why do you increment ans where you do?
4. return ans-1 is what we call a kludge. Fix the problem that causes ans to be too large.
Other than that it seems to work fine, albeit with the parameters reversed. (But that's not really your fault; who understands what target and key mean when searching for strings?)

Now, the recursive version:
1. Why pass check to the find function? It can only be 0 at that point, which has the same effect as omitting it.
2. What is your base case, and what should the base case return?
3. Why increment check by searchLength?
4. When slicing a string, if you want everything to the end of the string you can omit the second index.
5. You're returning the return value of the recursive call, which will only ever be the base case return value.
Other than that you're recursing down to the base case properly, and returning from it properly. It's just some details about the trip there and back that are incorrect.

Answer 2

Okay, I'll answer them one by one and we can see why I'm doing what I'm doing wrong, maybe that will help.

1. I Compared the boolean to end the while loop. I guess, after looking at the help you gave me on my last assignment I could just write that line while isFound: huh?

2.I add 1 to the answer so that the next time it iterates it starts the find operation 1 character after the last key that it found. Is there a better way to do this? I.E. It's looking for 'abc' in 'abcdefabcdefabcdef', the first find returns 0, so, without incrementing it, the second find also returns 0.

3. I incremented ans there because it was immediately after it found a match. Is there a better place that I'm missing?

4. This one's probably the crux of the matter and attacking this problem is probably also the answer to the prior two questions, I'm sure. The reason the -1 is there is because it runs through the while loop one time pass the rest because it has to find a no match to break the loop. I'll have to think about this one.

I'm gonna take your suggestions and questions and make a second attempt here. I'll post some code in a few.

-Ian

Answer 3

Okay, I started fiddling with it. Got most of the iterative piece figured out. Heck, 2 outta 3 ain't bad, right? Still not sure about what to do with that +1.

I'm still a little backward on the recursive part though. Okay, so obviously the base case is when it doesn't find a match, which should be a return None, right? So its recursively makes it to the base case, but returns a None, than it just returns a None each rung of the ladder, right? Or is this the important part I'm missing? Again, I incremented check by the search length to prevent getting stuck in an endless loop. It finds a match, slices the string at that point, than sends that string into the function again. I know there's probably a simple answer to what I'm missing, but I'm banking my head against it I think.

Anyway, here's the code now.

http://codepad.org/UkLgEfwo

-Ian

Answer 4

for the recursive function:
you are slicing the key instead of the target.
when you find an instance, you want to add one to the results from all deeper recursions.
you stated the base case above but didn't implement it - if you don't find an instance, return zero

Answer 5

I'll respond to your responses to my questions first.
1. Exactly.
2. Yes. But, as a style point, I regard the value a function returns as sacred. I don't want to mutate it, because then when I need to use it I need to unmutate it. That's messy. The way I try to it is to save the returned index, and when I call find() the next time I pass it index+1 as the last parameter. Again, it's just a style issue, your way works, and you know why it works, and the function works, so I can't complain (too much). I just usually struggle to keep that return value pristine. You have to think about who will read the code after you write it. -1 is the traditional flag value indicating that a find didn't find anything, and I don't want to violate the reader's expectations.
3 and 4. Your new code fixed this. You were incrementing it even though you didn't know for sure that there was a match. Check the return value before declaring a success.

But, this is all about the iterative implementation, which is working. The recursive one is where you're having trouble. So let's get to that.

Answer 6

Like I said, you're making the recursive calls correctly, and detecting the base case correctly. You're just not returning the right stuff.

What exactly is countSubStringRecursive supposed to return? An integer, yes, but what does the integer mean? (It's supposed to return the number of times key is found in target.)

Given that stated contract for the function, what should each recursive call to the function return? (The same thing: the number of times key is found in target. Even though target is a smaller version of the previous target, it's still the target.)

What base case are you detecting? In that case what should the function return? (Remember the contract for the function.)

During some trip through the function, you search for key in target. When you find one, you then recurse on a smaller version of target. Why? What is that recursive call doing? What should it return? What should you then return from this trip through the function?

You said, "Again, I incremented check by the search length to prevent getting stuck in an endless loop." But that's not how you avoided the infinite loop in the iterative case. How did you? What's the difference between the two things you did? Which approach does the problem set want you to use?

Style issues:
1. You set check to 0, then clobber that value with the return value of find. You don't need to initialize check.
2. stringLength is not used in the function, so you can get rid of it.
3. Use += to increment check by searchLength.
4. You have key and target backwards from the problem specification. You're confusing everyone who's already done this problem. Stop it. ;)

You're doing a good job understanding and implementing my suggestions. I only write so much because I think you'll actually read it and benefit from it.

Answer 7

http://codepad.org/RqBTh5Uq

Of course, I began writing out this long reply because I still didn't get it, and somewhere along the way I was walking through your answers and came up with the recursive answer. Seems to work, any other thoughts about it?

One question about the iterative function though. I made the style change you mentioned (check + 1), but now, if the key happens to be the beginning of the string, it will miss that one, i.e. x='abcdefabcdefabcdef', searching for a key of 'abc' returns 2. How do you maintain good style and still meet the intended goal?

BTW, thanks for all the help, I do appreciate the long answers. I don't get much time to put towards the class because of a full-time job, but I am committed to making my way through it. Programatically looking at problems is a much better way to approach things.

-Ian

Answer 8

Here's the same code with comments, too much, too little?

http://codepad.org/JV6AcFI2

-Ian

Answer 9

Excellent progress!

In the iterative version you say you're missing the first match. What are you passing as arguments to find() the first time you call it? Specifically, what's the value of the third argument (where to begin searching)? What do you want it to be? How can you make it be that, but still keep the "+1"?

http://codepad.org/SVxYgRt1
Here's a test suite you can use to debug both functions. If the tests pass it prints nothing. Otherwise it prints the discrepancy.

The iterative one is wrong because of the problem you mentioned. Hopefully my questions will lead you to how to fix that.

The recursive one is wrong for another reason (not because of the mechanics of the recursive process, which you got correct). The last two test cases I gave will illustrate the problem.

Answer 10

Well that was easy. Kind of like looking down at the breadboard and realizing you don't have ground hooked up after troubleshooting the logic analyzer for like an hour.

Thanks.

http://codepad.org/ThJT2gWA

Answer 11

The best part is that once these two functions are in the bag, the rest of the assignment is pretty much done. I guess that's the cool part of all of it is that with more basic functions you can do some pretty awesome stuff. Thanks again for all the help. I'm sure I'll need more as the lessons progress but probably a lot less with the knowledge gleaned from this.

Answer 12

http://codepad.org/0LdcZRkq
Here I just merged some code and made it a little smaller. I also added a few extra test cases, for edge cases.

You will use these functions in the later problems (in this PS), but the questions do get harder. I would definitely not say it's "pretty much done." But you know you're learning when you solve hard problems. Good luck!

Answer 13

a little different:
http://pastebin.com/9N9peYq5