#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2011
    Posts
    2
    Rep Power
    0

    How to avoid variable reset in a recursive function


    Hello

    I'm trying to write a piece of code (in Python) such that it takes a string (target) such as 'atgacataccaagtatg' and a substring (key) and counts the number of times key exists in target.

    I already have an iterative version of the program, so that's not the issue. I want to learn how to deal with this problem recursively as well.

    The issue is that I can't get the variable 'total' to not reset everytime it calls upon the function again.

    Code:
    def countSubStringMatchRecursive(target, key):
        position = string.find(target, key)
        total = 0
        if position >= 0:
            total = total + 1
            target = target[(position+len(key)):]
            countSubStringMatchRecursive(target, key)
        elif len(target) < len(key) or position == -1:
            return total
  2. #2
  3. No Profile Picture
    Lost in code
    Devshed Supreme Being (6500+ posts)

    Join Date
    Dec 2004
    Posts
    8,317
    Rep Power
    7170
    The point of a function is that its variable "reset" every time it is called. In some programming languages it is possible to have variables that don't reset, but this is not an appropriate solution to your problem. (And I don't program program in Python so I don't know whether or not Python supports this)

    What you need to do instead is use the return value of the recursive function. For example:

    Code:
    def countSubStringMatchRecursive(target, key):
        position = string.find(target, key)
        if position >= 0:
            target = target[(position+len(key)):]
            return 1+countSubStringMatchRecursive(target, key)
        elif len(target) < len(key) or position == -1:
            return 0
    (or however you would correctly write this in Python)

    So now when your function call hits the bottom of the recursion stack it will return 0 because there are no more occurrences of key in target. Then the second from the bottom call, which represents one match of key, will return 1+0, then the third from the bottom call, which also represents one match of key, will return 1+1, and so on. So by the time you reach the top of the stack, your function is return <number of function calls>-1, which represents the number of occurrences of key in target as I understand your code.
    PHP FAQ

    Originally Posted by Spad
    Ah USB, the only rectangular connector where you have to make 3 attempts before you get it the right way around
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2011
    Posts
    2
    Rep Power
    0
    Originally Posted by E-Oreo
    The point of a function is that its variable "reset" every time it is called. In some programming languages it is possible to have variables that don't reset, but this is not an appropriate solution to your problem. (And I don't program program in Python so I don't know whether or not Python supports this)

    What you need to do instead is use the return value of the recursive function. For example:

    Code:
    def countSubStringMatchRecursive(target, key):
        position = string.find(target, key)
        if position >= 0:
            target = target[(position+len(key)):]
            return 1+countSubStringMatchRecursive(target, key)
        elif len(target) < len(key) or position == -1:
            return 0
    (or however you would correctly write this in Python)

    So now when your function call hits the bottom of the recursion stack it will return 0 because there are no more occurrences of key in target. Then the second from the bottom call, which represents one match of key, will return 1+0, then the third from the bottom call, which also represents one match of key, will return 1+1, and so on. So by the time you reach the top of the stack, your function is return <number of function calls>-1, which represents the number of occurrences of key in target as I understand your code.
    You're right, the issue was that I didn't completely understand how return worked.

    Thanks a lot!

IMN logo majestic logo threadwatch logo seochat tools logo