Question

Hi,

I've been working on ps3a, going crazy trying to understand recursive functions.

I've gotten here:
http://codepad.org/AzyacRwQ
but I'm not sure if it is correct.

Can someone have a look and give me some feedback?

Thanks

Answer 1

looks like you have a good starting point
- 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

at line 34 you reduce the size of the problem - check
lines 27, 29 and 41 suggest you know when to stop - since this is a counting problem, the function should probably return zero if key is not in target

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/
a counting example - it is a spoiler http://dpaste.com/716366/

Answer 2

Hi bwCa,
thanks a lot for taking the time to look at my answer. Your tips really helped understanding recursion. I think I got it now!

Without looking at the spoiler I arrived here:
http://codepad.org/EW13jPek
What do you think?

I tried to get the reducing the target size into the return part of the function but I didn't manage to get it to work. Would it be possible to do that?

Answer 3

lines 31 thru 39 look like they find the count all by themselves without recursion
i don't see a base case for stopping the recursion - do you get a maximum recursion depth error?

you need to abandon lines 31 - 39, they don't belong in the recursive version. you need to figure out how to do the same thing with the recursion -

every time you recurse you create a new instance of the function with only part of the original target.
if you find the key you add 1 and recurse passing part of the target
if you don't find the key, you add 0 (and stop the recursion)
- not finding the key is the base case

Answer 4

Hi again bwCA,

thanks for you patience, I was really having difficulty in letting go of the counter variable. I think I got it now:
http://codepad.org/F62eDTUf
It is amazing how elegant recursive functions can be, I was just cutting and cutting lines of code.
cheers,
Luis

Answer 5

http://codepad.org/v1MmWdAQ
You should use the in and not in operators when applicable - i don't really know why but numerous reference say that

the else statement at line 24 is not necessary - in a function if you have a return statement in a conditional, it makes the else superfluous, this pattern appears often

Answer 6

Hi,

Thanks!! you've been really helpful in understanding recursion. And in trimming down my answer to the bare essentials.

All the best,
Luis