Question

ps3a - in need of some refactoring. specifically, how do you rewrite the function to only take 2 arguments and still work?
http://codepad.org/ujKGIGOA

Answer 1

I don't think you need to initialize x as an argument, you can just set up x = find(s,p) because find already returns a value. If this is the recursive version (as I assume), what I did is that I initialized x = find(string, pattern) inside the function and then I sliced the string s in s[:x] + s[x+len(pattern):] if x!=1. But I think your code looks good :-). Congrats on the solution

Answer 2

I agree with bmp. The parameter list should stay the same as in the problem set. The recursive step should reduce the problem, which I think means reduce the size of the string to search (that's the only way I can see to do it without adding another parameter).

And you shouldn't be using a global variable. Now that you're using functions you should use local variables almost exclusively. Instead of keeping track in a global variable, on each trip through the function you should take the result of the recursive call, and modify that result for the work done by this trip. (Did that make sense?)

Also, you have a return statement, but it's not returning what you think it's returning.

Answer 3

I shortened the code by andreipop, but that was before reading bmp and dmancine . How you would improve on this? http://pastebin.com/b0CuixSs

Answer 4

@jprichter, I don't see how that code is different from the original code in any meaningful way. So, it still suffers from the problems bmp and I mentioned. So, to improve on it, I would start by trying to implement our suggestions.

Answer 5

I'm missing something here, but I'm not sure what. http://pastebin.com/Hf7PKHYi

Also, I don't know how to get recur_counter out of the function without making it a global variable.

Answer 6

All you have to do is use a while loop and modify x internally with x = find(s,p):
http://pastebin.com/RtYUXn6f
:-)

Answer 7

@bmp He's trying to write a recursive function.

@jprichter No, you can't just take it out of the global scope and hope it'll work. You have to rethink how to solve the problem with a recursive solution. A recursive function will do one part of the problem itself, and pass the rest off to a copy (recursive invocation) of itself. When doing so, it trusts that the result of the recursive call will have the solution to that rest of the problem. So it just adds its little result to that and returns it.

They went over a recursive factorial example in lecture. Did you understand that? Because that's the simplest example of recursion. I'd say don't try this string problem until you understand the factorial one.

Answer 8

I mean, I answered the second part of the question, but yeah, I misinterpreted his question. My bad. Anyway, dmancine, how is the correct naming for the recursive function calls? I mean, can I think of it abstractly as a stack, where the base of the stack is the base case and the calls "unwrap" or "reduce" the stack once at a time?

Answer 9

still couldn't figure out out to do it recursively without using a global variable. http://pastebin.com/Hf7PKHYi

Answer 10

@bmp Yes, function calls are always put onto a stack. That's always how function calls are implemented. And there is talk of "unwinding" the stack (like in the case of an exception that travels up several stack frames). And the terminology to use when talking about stacks is "push" and "pop". You push things onto the top of the stack, and pop them off from the top of the stack.

Having said that, the recursive calls can act like different structures, like in the dpAdvisor problem, or the brute force Fibonacci implementation. In those cases it's more like a call "tree" where each call can have multiple "child" calls. But the interpreter always just uses a stack (it's essentially doing a depth-first search on the call tree).

When I'm talking about recursion (like in this case) I usually say something like "recurse down" to the base case. And after hitting the base case it "returns back up" the call stack. Maybe it "passes the return value back up" the call stack.

Answer 11

@jprichter You're returning the value from the function. But within the function you're not using the return value of the recursive call. What will the return value of the recursive call be? Hint: print out the return value.

Answer 12

@dmancine Thanks for "use the return value of the recursive call." It was exactly the hint I needed.