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

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 5 Years Ago by Gribouillis: n/a

Comments
nicely said

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 article has been dead for over six months. Start a new discussion instead.