Question

working on Prob.Set 3 question 1. got the iterative part done but wondering how to set up the recursive so it doesn't run infinitely. seems like I'd have to pass in the index of where I am in the target string.

Answer 1

Do you have any problems conceptualizing how a recursive function should work? If you think more clarification would be interesting, I will try to make a point from there.

Answer 2

my understanding is very basic... run base test, if true then return, otherwise, call self. I guess I must pass an incremented (or decremented) parameter? I'm just not sure how this would work. The other thought I had was passing part of the target string (i.e. subtracting a character each time) if that were possible... ??

Answer 3

Loosely speaking, a recursive function should have a base case, that returns a sensible result that will unwind the rest of the stack (I will come back to this later), and a recursive function. In Python, it should look something like that:
def fact(n):
if n == 0 or n == 1: return 1 #base case
else: return n*fact(n - 1)
What happens when you call fact(5)? Your program will create a frame in the stack for the initial function call and when it reaches the else clause, the function will be put in a halt for resolving the statement to return. In the first frame, you will have 5*fact(4). Now, another frame will be created for the fact(4) call that will resolve in 4*fact(3), and so on, until you reach the base case, that will return the sensible value of 1. All the frames will resolve (last to first), and your result will be 5*4*3*2*1
An important thing to realize is that you didn't calculate 5! directly. Your program does not understand what is the mathematical operation behind 5! He knows how to solve fact(5), a recursive function that always end.

The most important realization when trying to grasp recursion is that your function should always reach the base case. It should always reduce the problem by a factor. In the factorial example, the problem was reduced by subtracting 1 in each subsequent call.

Now, in our string case, your intuition is correct. You should be able to "remove" characters. But you shouldn't remove one at a time. Now, string slicing enters into play. You can do something like print foo[1:3], and this will print the [1,3) characters in the string, assuming foo is well defined. Now, remember that find() returns the initial index of the first occurrence of the pattern. You have the length of the pattern (remember, len(pattern) ?) Can you see where this is going? You have to pass a target that removes the occurrence.

P.S.:Also, look into concatenating strings in Python. Should give some ideas to you.
P.S.2: I am sorry for this TL;DR version. I think that recursion is beautiful, and really like to talk about it, but I also find it confusing at first, so I am more prolix than normal to try and make a point. If I was unclear in some points, go ahead and ask away :-)

Answer 4

- a recursive function 'calls itself'
- a recursive function needs a 'base case' which is a condition that stops the recursion
- reducing the size of the problem for each recursion seems to be a good practice

the in (and not in) operators are good to use:
http://docs.python.org/reference/expressions.html#not-in
http://python.net/~goodger/projects/pycon/2007/idiomatic/handout.html#use-in-where-possible-1
http://dpaste.com/716360/

so you want to stop recursing when the key isn't in the target.
on each recursion if you find the key in the target you want to add 1

another tip
http://python.net/~goodger/projects/pycon/2007/idiomatic/handout.html#testing-for-truth-values
http://docs.python.org/library/stdtypes.html#truth-value-testing

here is a recursion example - http://dpaste.com/716372/

spoiler - try to figure it out first
a counting example - http://dpaste.com/716366/

Answer 5

Thank you BMP and bwCA! Both of these explanations were extremely helpful. I have a MUCH greater understanding of how to set up a recursive algorithm. I will save your comments for future reference. Again, thanks so much!!! :)