How does incrementing the variable count by the recursive call to the function, save count from being reset to zero everytime it is invoked?
I am trying to get a firm understanding of how recursion works.

``````def countSubStringMatchRecursive(target,key):
"""Searches for instances of the key substring occuring inside the target string.
Returns the count of all occurences of key in target."""

count = 0               # Count of occurences found.
found = -1              # Stores result of search
i = 0                   # Index into target to begin searching.

strTarget = str(target) # Insure that target is a string type.
strKey = str(key)       # Insure that key is a string type.

# Guard against empty target or key.
if strKey == '' or strTarget == '':
return 0

if len(strTarget) >= len(strKey):
found = strTarget.find(strKey)
if found > -1:
count += 1
count += countSubStringMatchRecursive(strTarget[found + len(strKey):], strKey)
return count``````
5
Contributors
4
Replies
6
Views
7 Years
Discussion Span
Last Post by pyTony

Each call to a recursive function uses a new set of local variables. It means the the inner call to countSubStringMatchRecursive will use another count variable, and the count variable of the calling function is not changed.

The simplest way to understand recursion is to think about it the way mathematicians think about proof by induction: Suppose that, for any shortest target string, the function returns the number of occurrences of the key. Then the line `count += countSubStringMatchRecursive(strTarget[found + len(strKey):], strKey)` actually adds the remaining number of occurrences of the key. And the proof that the function works follows by induction.

Edited by Gribouillis: n/a

nicely said

All said Grib !

;)

why don't you use the re module

``````import re
def countSubStringMatchRecursive(target,key):
return len(re.findall(key,target))``````

The OP obviously learns about recursion as programming technique. The code is against the Python-do, but let it be... Grib gave good answer, let him learn style in peace after.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.