Question

Recursion... I'm trying to do ps3 part1b. I'm not looking for answers (yet) but I can't see a way to pass any kind of iterative count through back to the start.
I need to intialise the variable before =+1, but that seems to reset the variable, so i can't pass...
is there a known strategy for iterating recursions in Python?

Answer 1

After continuing to work on this, I see that once you return something, it just returns up without reading the program. But it also doesn't work on the way 'down' because even if I find a way to initialise only under certain conditions, and add one, then when I call the function again I can't pass the argument, so it has to be re-initialised, and isn't aware that I have added one.

Answer 2

first:
post your code, dpaste.com. its hard to know what your coding by description alone.

second:
you don't iterate recursions, that is what this problem is about, keeping the two things separate, learning that there is more then one way to do something, and letting you choose which. I strong believe your just going about this the wrong way

third: there is a way to get around initializing a variable in the loop, make it global. but then it needs to go back to zero, you could also try doing a
countSubStringMatchRecursive(target, key, total = 0)
this lets someone call the function using only two arguments, but lets you pass a third for your own purposes, be aware this lets people muck up your output a lot easier

Answer 3

1) yeah, fair enough. This is the code: http://dpaste.com/556140/ (oops I forgot import string) I've been working on. A bit futile as I am going to abandon it, but I guess it illustrates what I've been thinking.
2) I'll come back to this
3) okay, thanks, I can see how to do it with the total=0 argument, and I can see the problems this could create if someone chose to try to enter an argument. Not sure what you mean by global. And yeah, if they are looking to break out of the iterative pattern, I'm not going to learn by ignoring that. (Thus, the abandonment.)

2 again) I probably am going about it all wrong. I can't seem to get my head around any other way. I've been thinking about the base case. The simplest case I can think of is there are no matches. So I can recursively remove matches, but I can't keep track of them. That is what I have been attempting.
Or, there is only one match. But how would I know that without using string.count? If I use string.count, what is the point of recursion?
Maybe I can use recursion to see True/False there is more than one? I will attempt this while I'm waiting for an answer or a bolt of inspiration.

I'm a bit stuck here. Any clues? Am I heading the right direction?

Answer 4

No, the True/False idea won't work, it'll just return True or False, not a count.

Answer 5

You are on the right track, you just need to figure out how to persist the count through the recursions. I think i remember some examples of how to do this in the lectures. Or you can look at the examples below.

Here is way to do it where the actual counting/addition doesn't happen till all of the recursions start returning after the base case (zero length string) is reached:
http://dpaste.com/556221/.

I read somewhere that there are two ways to do this; one where everything happens as the recursions are returning and the other when everything happens as the function is recursing - there are tradeoffs between the two.

(methods suggested by senior nessman)
using a variable outside the function (global): http://dpaste.com/556222/
passing the count to each recursion: http://dpaste.com/556225/

Answer 6

strings have there own find method, you don't need to import string. Try this in idle:
'asdsdfdfgfghghjhjkjkl'.find('df')

Your base case (lines 16-19) looks close but your target may never get to zero length.
Maybe your base case should be something different?

count += 1 should not be in the same if clause as your base case, it should be in the same clause that recurses further.

Answer 7

I just thought of an improvement to version 2, so if you are thinking of debugging it, hold off.

Answer 8

problem set 3 gave me the most trouble out of any of the problem sets thus far...
heres my solution:
http://dpaste.com/556345/

Answer 9

EDIT: my posts are getting messy, so I'm editing and merging...

@BwCA (and others)
Those examples are fantastic! The global is pretty weird, the count behaves very strangely if you run it again it adds on. The added argument works but is not that safe, but the first is quite solid and a very good tool to have I think :)

I did re-watch lecture 4 and re-read the readings but I couldn't find anything about iteration in recursion. Maybe I missed it but I was looking for it.

Good to know about the inbuilt method for finding strings.

In the program I pasted, there was kind of 2 base cases, due to the attempt to find a way to pass iterations. (It was unsuccessful). But the first is supposed to be the first 'base case', where I initialise the count and then remove any of the string left over, and the second is for the rest, as I removed the string characters, thus it is supposed to add the count, but it doesn't as the program doesn't read on the way up. I had previously tried the count on the way down, which didn't work because each new call was ignorant that it had been initialised. I am now going to attempt to fix that program based upon example 1.

@jmbauer (and others)
Hey thanks jmbauer! I will definately check it out, right after I try out a couple of things, I'm sure even if I get mine working properly it isn't the best way. I'm looking forward to seeing other answers but I want to tidy my ideas first.

@Nessman (and others)
I left my reply to your post above BwCA

@ All

Meanwhile, last night I did come up with a different way, but I feel it is still wrong as the base case involves calling a funtion, so therefore isn't the simplest version. Does this make it 'bad practise'? It isn't working, and the reason is in the isAllKeys function, it returns 'None' even though it enters the 'True' loop. I'd love someone to look at why it is doing that.

http://dpaste.com/556349/

(Again, I haven't put import string and I haven't played with the format BwCA said yet so it needs it.)

Answer 10

i was looking at this one
def allKey(target, key):
"""is the Target all a series of keys?"""
print "has entered allKey"
if target == key:
print "True"
return True
elif target[:len(key)] == key:
checkTarget = target[len(key):]
allKey(checkTarget, key)
else:
print "False"
return False

i think i know whats wrong with it or did you figure it out?

Answer 11

No, I don't know. The new one I posted is the same with a new name and attached to the count function, that's all.

Answer 12

heres what its doing for ('nana','na')
the values 'nana', 'na' enter allKey
Elif is called because the beginning of target until len(key) is same as key
when you call allKey(checkTarget,key) its saying the checkTarget which equals target[len(key):] or in otherwords na and then enters allKey again through the recursion
has entered allKey
then prints true because na == na which is your first if statement...

did that make any sense?

Answer 13

Yep. It prints True, which proves to me that it enters the first if, as you say. Why then doesn't it return 'True', which is the next instruction?

Because it returns 'None'.

Answer 14

what do you mean it returns 'None'? here's what im getting:
>>> allKey('nana','na')
has entered allKey
has entered allKey
true
>>>

Answer 15

the true it says there is because of the line 'print True' which would have been less confusing if I had written 'print 'has entered the if statement''.

But it returns 'None', if you put allKey('nana', 'na') == True you will get 'False' if you put allKey('nana', 'na') == None you will get 'True'

I'm trying to use it as a boolean condition in the main function, but calling it won't determine true/false, because the output is 'None'.

Answer 16

oops...

http://dpaste.com/556355/

clearer example. copy/paste the comments at the bottom and you will see what I mean. I think.

Answer 17

yeah i see what your saying, that's strange... it's annoying me too so im going to keep trying to figure it out

Answer 18

It is weird but there must be a reason. I have also tried return 1 and it does not return 1, it returns 'None' still.

Answer 19

yeah i made a test function that tests ('nana', 'na') which returns none ('na', 'na') which returns true, ('nana', 'nana') returns true and ('nanananana', 'na') which again is none so it looks like it has to be right the first time which doesnt make sense

Answer 20

and btw if you put ('nana','f') it returns false so i guess you could just use none as part of your answer like if answer == none print "true"

Answer 21

oh, okay, that is clarifying a lot, but actually, the main function needs to know if it is a series of nananananana then it is correct and will fail if it can't determine that... :)

and anyway it is still boggling me, I would suggest there is something wrong with the recursion but it enters the if...

Answer 22

Actually, I changed the condition so that it != False and that works for the program.

But it still doesn't make sense. I might leave it alone for a while and hope something comes to me...

Answer 23

yeah that's confusing, why does it go to the if statement for both != and == in the first place?

Answer 24

Oh wait - I changed the != false in the main program, to make the main program work (haha and I found another issue...) not in the isAllKeys program.

isAllKeys remains unchanged and strange...

Answer 25

so you didnt change this....
if target == key: to this if target != key:

because if you do then it returns True

Answer 26

Oh what? It decides to read the return if I put !=??? This is doing my head in.

But that means 'nananajj' is also true. and 'na' is false.

Answer 27

I'm getting off the computer my head is going to explode.

Answer 28

lol i have no idea whats going on hopefully someone can clarify soon

Answer 29

o i found your answer: http://dpaste.com/556360/

i think it's because after it enters the elif branch, it has no return statement following it, so it will return None. Put another way, once it is done executing all of the recursive calls from the elif branch, it won't execute the if or else branches again, so it will continue with the rest of the function, which is nothing, so it will return None.

If it's still confusing, imagine just one pass through the function with no recursion. If you enter the if branch it will return True, if you enter the else branch it will return False. If you enter the elif branch, it will exit the conditional statement and return from the function. When no return value is explicitly given, a function will return None.

from python-forum.org

Answer 30

If there was a way of displaying fireworks.. lol... I would.

I thought, obviously, that it go through each time, so it seems it doesn't, and so we both learnt something from that...

Nice link, too!

I just couldn't keep away... lol but I'm glad I checked again. Still, I was working on this all last night and dreamed about it and now all day so I will investigate it and fix up the code later. Thanks so much for your help!

Answer 31

no problem, better to learn now before i run into the same problem lol

Answer 32

Wow you have all helped so much I have now got 2 complete programs which appear to work swimmingly.
One is based on BwCA's example 1 (iterative recursion) and is here: http://dpaste.com/556382/

The other is: http://dpaste.com/556381/

The only thing I really have left to ask on this is whether the second is a 'proper' use of the recursion method? The base is not simple. But then again, the function called takes it back to its simplest form.

Anyway, thankyou all SO much for your help!

Answer 33

it seems that your base case condition, line 29, could be be simplified to just:
if isAllKey(target, key):

isAllKey returns True/False so you don't necessarily need to compare it to True or False

isAllkey would only return True if target begins with the key

Answer 34

Ah yeah, I removed the unneccessary True qualifier, thanks. (A bit like ATM Machine...lol)

The other part of the condition is to reduce the amount of times it has to go through the isAllKeys function. But, yeah, it would make it simpler.

Answer 35

:)

Answer 36

to your question "is this proper", the answer is
does it get the job done?
does it run as fast as you want it too?
in that order of importance, if it solves those two, your golden. i do have to say i really like your first pieces of code, i gotta say i didn't think that's what you meant by iterative.

Answer 37

Thanks Nessman :)