Question

Ps3 problem1 (recursive):

I think I have the idea of this but can't put it into code.

the base would be target==key, so then I would check the key length of the beginning and end of target and see if those ==key, and then remove them and repeat?

Is that the right train of thought on this?

Answer 1

the base case could be different things depending on how you tackle the problem.

one thing that is often done in recursion is to reduce the size of the problem each time you 'recurse'. if you take this approach and reduce the size of the target each time then the base case might be that the key is not in the target.

Answer 2

Figured it out (with help!): here is what I have -> http://codepad.org/l9oAOZgH

One thing I can't figure out, is it possible to keep track of the locations of keys within the target in a recursive function?

Answer 3

I was able to do it. I treated it like the count. Instead of returning a number you return a structure (a list). And instead of just adding 1 to a count you're appending an element to a list.

Actually, it gets a little more complicated. Since the recursive call shortens the string, you don't have the absolute position within the original string when you're in a recursive call. I was able to handle this without adding another parameter to the function. Also, if you just append the items to the list they'll come out in reverse order. You can use insert(0, item) to "prepend" to the beginning of a list.

It's not strictly part of the problem set, but it's an interesting problem, and solving it is certainly instructive. If nothing else it'll give you a little practice for PS8 problem 4.