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

Recommended Answers

All 4 Replies

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.

commented: nicely said +13

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.