Question

I am working on problem set 3. Here's the code I wrote for a recursive string matching program. It endless loops, and I can't figure out why. Any ideas? Thanks!

def countSubStringMatchRecursive(target, key):
count = 0
n = 0
length = len(target) #how long is the target?
if n >= length: #check if the target has been completely checked,
return count # and if so, return the instances of "key"
else:
if key == target[n]:
count += 1
n += 1
countSubStringMatchRecursive(target, key)

Answer 1

Working recursively, your function should always return a result, either a scalar value (end case) or a call to itself with modified arguments. In your example however, you only return a value on the final case, and all other cases are called with the same arguments. Basically, modified your last line to be a return of a function call, rather than a plain function call, and make sure that you're just calling the function with the same values over and over.

Answer 2

modify last line, not 'modified'. I promise I can english.

Answer 3

Thanks for the reply - do you mean the last line should read:
return countSubStringMatchRecursive(target, key)

I tried this, and I am still getting an endless loop.

Also, what is the difference from calling a function inside of a function and "returning" a call of a function inside of a function? Would these not be the same thing?

Thank you.

Answer 4

Almost, the last line definitely needs a return, but you still have to modify the arguments being sent to it also. You're not making any changes to target or key before sending them back into the same function. The difference between calling a function and returning a function is the result. Suppose someone asks you what time it is, but you don't have a watch, asking someone else (calling their check time function) may give you the answer, but that's not the scope where the answer is needed, you need to return that answer to the original asker.

Answer 5

Recursive functions need to handle three scenarios: What to do when it should recurse, when it should stop recursing and "unwind" ( basically unrecursing ). and what to do when it's "unwinding".


countSubStringMatchRecursive(target, key):
if( len( target ) ):
match = 0
if( key == target[ 0 ] ):
match +=1
return( match + countSubStringMatchRecursive(target[ 1 : ], key) )
else:
return 0