Question

problem set 3a - recursive part. I can't count the number of times "atgc" is found because whenever I call the function again it resets my count to 0 as per my declaration: http://codepad.org/Z8uzT0Ud

Answer 1

The way I originally got around this is to make count a global variable. Doing this initializes count outside of the function, allowing you to increase it and preventing it from being reset to 0 each time the function is called. For a walkthrough of a recursive function that I found helpful see: http://en.wikibooks.org/wiki/Non-Programmer%27s_Tutorial_for_Python_2.6/Advanced_Functions_Example

Answer 2

btw, the tutorial link does not have anything to do with global variables...sorry if that caused confusion...it just helped me to understand recursion better as well as a solution I found that did not require using a global variable. After you get your version working w/ a global variable, I can show you the alternate solution, if you would like. I am not sure I would have ever come up with it, without seeing first (not to say you couldn't).

Answer 3

Yea I kind of want to do it without using the global variable, because I get the feeling that the way I implement the recursive function isn't exactly proper. I'll give this a read and see where that takes me.

Answer 4

Still lost. I think I am thinking about it iteratively and can't really get into the recursion mind space.

Answer 5

Well, like I said, your current approach is similar to the way I went first, which did lead to the right answer (when using a global variable). I do have a couple pointers (take them for what they are worth coming from someone on the same problem set who has little other programming experience):

1. Import the string library at the top of your code rather than within the function. This will call it for the entire program (useful in the next couple problems which will include multiple functions using this library) and keeps your function tidier.

2. There is no need to initialize index = 0. It is initialized when you set it equal string.find(target, key) and nothing happens to it between it being set at 0 and the reassignment.

3. For the sake of simplicity, it may be clearer (and use fewer cycles) if you make your "if" statement deal with your base case (index == -1). Then under your "else" you can recall the function and up the counter. This way you only up the count when you want it to, rather than upping it everytime and then subtracting if the increase was unwanted. This will still do what you are doing already, but will make it look more like the recursive functions in the examples and possibly help you feel better about your solution.

4. When recalling the function, you can incorporate your string slicing right into the function call. E.g., countSubStringMatchRecursive(target[(index+4):len(target)], key) if using your code. This obviates the need for the declaration of the target variable in you function.

I hope these help.

Answer 6

Also, from what I can tell, recursion and iterative methods are similar. You may feel like you are thinking iteratively, but still come up with a recursive program. A recursive function is simply a function that will call itself (thus using itself to break up a problem) (See How To Think Like A Computer Scientist Chapter 11). In the sense that the recursive function at hand is supposed to call itself until it finds no more instances of the key within the target, it is iterative (it repeats itself). Given that you have done that, you have a recursive function (afaik).

Answer 7

Did you get it? Point 3 from cb12's above points explains the part I was having trouble with. However, I have a different perspective with regards to point 4. First, len(target) is unnecessary as leaving it blank after the colon will accomplish the same function. Second, I believe the function should be called with target[index+1:] rather than with target[index+key:] as the index+4 answer is suggesting although this could certainly be up for debate. According to my method, if I'm searching for a key such as "aa" and I have a string with "aaaa" in part of it, I will find it 3 times whereas the other method will only find it twice. Nevertheless, thank you very much cb12 the tutorial you referenced as that helped me finally figure it out.

Answer 8

No problem, mengland74. I am glad it helped. Also, I agree that you would really want to slice the string and have the new target string begin with the first element after the beginning of the key tha was found previously. I was merely working with the code that dvena had created up to that point in an attempt to illustrate that those two lines of code could be consolidated.

Answer 9

I ran into the same problem. The only way I can figure out how to do it recursively is to set a the counter globally, which doesn't seem right since you don't want to have to worry about setting global variables every time you use a function. It feels like I'm forcing iterative thinking into a recursive program. I know technically it's recursive, but intuitively it doesn't seem like the same concept as the examples we've seen. Anyhow, here's what I came up with: http://codepad.org/9tMe8AMJ

Does anyone have an example of how to do it without a counter?

Answer 10

@W01f. There is a way to do it without setting the counter globally. You can set matchCount = to your recursive call + 1 in the part of the function where you want the count to increase. Also, I had a look at your code and noticed that it will not currently find a match if the key string begins at the beginning of the target string (i.e., the key begins at target[0]). If you were to change the if find(target, key) != 1 from a 1 to a 0 it should be remedied.

Answer 11

I'm not sure I get what you mean. If you're saying what I think, the final return of matchCount will just loop the program until it errors since the if condition that stops the recursions doesn't do its job.

Thanks for spotting that error though. Note to self: Test programs more thoroughly.

Answer 12

Rather than setting matchCount globally do this:
matchCount = countSubStringMatchRecursive(target, key) + 1

On second thought, I just tried the above with your code, and it caused errors stating that matchCount was being referenced prior to assignment. I am still too new to be able to tell you why, but I can tell you that the line you see above can be implemented into code and work (as I have done it).

However, if you you would like to alter your code in order to allow you to stop having to call a global variable, I have a couple suggestions. Essentially you can get rid of your outer if statement by implementing a base case. The base case is simply the case that causes the function to stop (here you want the function to end if key is not found in target). This could be the if branch of an if/else. Note that this branch would not have a line of code containing a recursive call. Then, in your else branch, you could use the above line of code I have given you.

To make it a little clearer here is some highly generalized pseudocode for what I am talking about:

if base case:
code that will stop the function
else:
recursive call plus up the counter

Answer 13

http://pastebin.com/9N9peYq5