Question

I have a problem writing a recursive function in ps3a. Here is my code: http://dpaste.com/hold/606247/

As you see, best I could do is to make it print "1" every time there is a match. I would like to use a variable instead for counting how much times key appears in target string (something like counter = counter + 1). Problem is, before using a variable, I have to assign it some value inside a function definition, so every time the function is called "counter" it will overwrite my "counter" variable preventing it from counting.

Can anyone help me to solve this problem?

Answer 1

I can get you a little further than that, but I'm also having a problem

http://dpaste.com/606268/

I kind of stole this from the internet, but nesting another function inside your first one allows you to add a variable (in my case n) which you can then add to as a counter. My problem is that when I want to return 'n' I don't get a value, even though when I print 'n' it works.

Hope that helps a little.

Answer 2

since the function returns the number of times it finds it you should add that to your counter and return counter
First the function initializes counter to 0 (REMEMBER each function call is a different scope)
Let's say there are four matches, the fourth match will increment it's own counter from 0 to 1 and add the last call which doesn't match (0) to itself making 1.
The third match initializes counter to 0, because it found a match it increments it to 1, then adds the return value of the fourth call (1) to itself making it 2 and returns.
Hopefully this helps.

Answer 3

http://codepad.org/KQfHK02Q My solution

it uses a variable nextindex to store the index of the place where target.find(key) begins to work.

if target.find(key) failed and evaluated to -1 (meaning there are no more matches to key in target) then the function returns a value of 0

else it calls itself to find the next instance of the key in target, beginning at target[nextindex]. Each time the key is found it returns one

countSubStringMatchRecursive('atttattaatat', 'at')
performs this:

1 + countSubStringMatchRecursive('ttattaatat', 'at')
1 + countSubStringMatchRecursive('taatat', 'at')
1 + countSubStringMatchRecursive('at','at')
1 + countSubStringMatchRecursive('','at')
0
1
2
3
4

and eventually returns 4, meaning there are 4 instances of 'at' in 'atttattaatat'

Your code just prints a series of ones because while you use tail recursion, you do not keep count of the number of times the function has found instances of key in target. Also, you do not return any value.

Answer 4

tombedor's code http://dpaste.com/606268/ is missing the return keyword; line 10 should be:

return countit(target[find(target,key)+1:],key,n)

That small change, and it should work perfectly.

His solution uses tail recursion, which does not involve any 'postponed operations' as a function is evaluated, which happens in normal recursion (my solution)

Without using the 'return' keyword, your function will work fine if you pass in arguments to countSubStringMatchRecursive that result in 0 (like '2523652', 'a') since countit will return a value of 0. Otherwise, it will return void (or None in Python) since countit calls itself without returning any value.

Answer 5

To drive my point further about http://dpaste.com/606268/

when you do this:

>> countSubStringMatchRecursive('123dhkjhf123kjhdfkjh123','123')

the function returns the value of countit('123dhkjhf123kjhdfkjh123','123', 0)

countit('123dhkjhf123kjhdfkjh123','123', 0)
returns None but after it calls
countit('dhkjhf123kjhdfkjh123','123', 1)
returns None but after it calls
countit('kjhdfkjh123','123', 2)
returns None but after it calls
countit('','123', 3)
returns 3

countit('','123', 3) will return 3 but since the other calls of countit are done without the return prefix, they won't successfully carry the return value of countit('','123', 3). Instead of what you expect, what happens instead is

countit('123dhkjhf123kjhdfkjh123','123', 0)

will call

countit('dhkjhf123kjhdfkjh123','123', 1)

but the value will not be returned to the original call by countSubStringMatchRecursive

when you put the return keyword it does this:

countit('123dhkjhf123kjhdfkjh123','123', 0)
returns countit('dhkjhf123kjhdfkjh123','123', 1)
returns countit('kjhdfkjh123','123', 2)
returns countit('','123', 3)
which equals to 3

so countit('123dhkjhf123kjhdfkjh123','123', 0) returns 3 through tail recursion

Answer 6

http://en.wikipedia.org/wiki/Tail_recursion

Answer 7

Thank you so much! This was giving me fits.