Question

For problem #2 in problem set 3, has anyone tried a recursive solution to subStringMatchExact? I have thought about it for days and I can only come up with this:

http://www.ideone.com/clone/lIDrF

I had to add empty spaces to replace the the sections that I spliced out in order for the find() function to throw out the correct indexes of "key". Any other recursive solutions, would love to see them.

Answer 1

I did not do a recursive solution for my initial work. The idea of a recursive function is to apply a function, reduce the problem, and repeat until done, but reducing the problem to me meant sending a substring back to the function. Creating that substring may only be a N complexity task, but it adds overhead to what an iterative function does quite tidily.

However, when I saw your question, I just had to do it! For fun, for learning, for the heck of it - whatever. I enjoyed your somewhat unconventional approach. Mine was a bit less elegant: http://codepad.org/U8i3PjtK

Answer 2

Thanks for sharing walkerp1, I totally agree with you that recursion'e efficiency seems to be constrained to few cases, but I have read that understanding how it works can make you better at programming, so I wanted to try it. Also, I am sure we will see recursion again and again in other courses. I am now working on trying recursion for problem 3 of the same set.

Answer 3

walkerp: that's another way to do it. my initial thought. :)
http://www.ideone.com/GvMrU and http://www.ideone.com/0Oeyv work
but does not work as can be seen @ http://www.ideone.com/NCIDq due to usage of 'target1' in the code

Answer 4

Also, an observation in line 18 and 19 of http://www.ideone.com/0Oeyv is
dlist = [len(target1)-len(target)+index] + subStringMatchExactRecursive(target[index+1:], key) is not possible, as a list cannot be added to a tuple respectively

Answer 5

what if the key consisted of "blanks"?

Answer 6

Shriram, a key consisting of blanks could potentially cause errors in my recursive function, I am looking for a way around this...will post revisions hopefully soon, thanks.

Answer 7

OK, I revised my recursive solution so that it will work even if 'key' is full of blanks or any character. This time I added comments to the function:
http://www.ideone.com/clone/o4Jzk

I had to make sure the character I was using to fill as placeholders in 'target' would not effect the find(target,key) function. Filling with a predetermined character would get me in trouble if that character was used as 'key', I added 26 (arbitrary) to key[0]'s ASCII sequence (ie. 'a' would become the character after 'z') which should cover all instances.

However, since we did not cover this in lecture, there must be a way to return the correct target positions as a tuple without having to use place holder characters. If anyone can think of a way to do that...I would love to see it, thanks.

Answer 8

here are a few variations
http://www.ideone.com/rfnTu