CODEWITHSUNDEEP
pythontail-recursion
Jagan
Jagan

Reputation: 11

Why do I get "Max depth recursion reached" in this recursive code?

I am very new to coding and stuffs. I was trying to implement the below code in python for a sentiment analysis task. However, My document is pretty big and when it tries to loop the documents through the function, I get an error stating Max depth recursion reached. I came to know after reading through blogs that the code calls itself in the return statement and that is causing the problem. Hence, Looking for some guidance or help from you guys from anything kind of pseudo code to rewrite the code. Find the code below:

def sentence_score(sentence_tokens, previous_token, acum_score):    
    if not sentence_tokens:
        return acum_score
    else:
        current_token = sentence_tokens[0]
        tags = current_token[2]
        token_score = sum([value_of(tag) for tag in tags])
        if previous_token is not None:
            previous_tags = previous_token[2]
            if 'inc' in previous_tags:
                token_score *= 2.0
            elif 'dec' in previous_tags:
                token_score /= 2.0
            elif 'inv' in previous_tags:
                token_score *= -1.0
        return sentence_score(sentence_tokens[1:], current_token, acum_score + token_score)

Upvotes: 0

Views: 89

Answers (2)

Roberto Trani
Roberto Trani

Reputation: 1227

I assume that your question is not about reviewing your code, but on how to change the recursive function in a standard function. The tail recursion is usually simple to manage because in some way you don't need to store all the results computed during the recursion, but just to accumulate them. In your case is even simpler because you don't need to accumulate the results.

You can change your code in the following way:

def sentence_score(sentence_tokens, previous_token, acum_score):
    while sentence_tokens:
        current_token = sentence_tokens[0]
        tags = current_token[2]
        token_score = sum([value_of(tag) for tag in tags])
        if previous_token is not None:
            previous_tags = previous_token[2]
            if 'inc' in previous_tags:
                token_score *= 2.0
            elif 'dec' in previous_tags:
                token_score /= 2.0
            elif 'inv' in previous_tags:
                token_score *= -1.0
        sentence_tokens = sentence_tokens[1:]
        previous_token = current_token
        acum_score = acum_score + token_score
    return acum_score

Update: The code above shows just how to translate the original code into a non-recursive code. As highlighted by @chris-hunt, this code (as the original one) may perform a copy of the list each time we perform the assignment sentence_tokens[1:]. Therefore, some easy optimization can be applied to the proposed solution in order to optimize the code. In particular, I think the following is the best we can achieve without knowing the details of the data structures you are using.

def sentence_score(sentence_tokens, previous_token, acum_score):
    for current_token in sentence_tokens:
        tags = current_token[2]
        token_score = sum([value_of(tag) for tag in tags])
        if previous_token is not None:
            previous_tags = previous_token[2]
            if 'inc' in previous_tags:
                token_score *= 2.0
            elif 'dec' in previous_tags:
                token_score /= 2.0
            elif 'inv' in previous_tags:
                token_score *= -1.0

        previous_token = current_token
        acum_score = acum_score + token_score
    return acum_score

Upvotes: 0

Chris Hunt
Chris Hunt

Reputation: 4030

Python doesn't have tail recursion, just use a loop instead:

def sentence_score(sentence_tokens):
    score = 0
    previous_token = None
    for current_token in sentence_tokens:
        tags = current_token[2]
        token_score = sum([value_of(tag) for tag in tags])
        if previous_token is not None:
            previous_tags = previous_token[2]
            if 'inc' in previous_tags:
                token_score *= 2.0
            elif 'dec' in previous_tags:
                token_score /= 2.0
            elif 'inv' in previous_tags:
                token_score *= -1.0
        score += token_score
        previous_token = current_token
    return score

this also avoids the function call overhead.

Upvotes: 1

Related Questions