CODEWITHSUNDEEP
python
dimitris1821gr
dimitris1821gr

Reputation: 5

Freezing while attempting to handle larger numbers within a recursion

I've been trying to create a Python program that calculates the Grade of Service of a telecommunication network using the recursive Erlang B formula: image

The program receives the traffic load and number of line services as input, generating said GoS as a probability. My issue is that when I am attempting to give a larger number e.g 30 for the line services and 5 for the traffic load, it freezes and shows no result. On the other hand, giving a lower line service number such as 10 manages to calculate said result. Is it perhaps related to memory leaks?

This is what I've written so far:

lines = int(input('Give number of service lines (s): '))
load = int(input('Give the number of the traffic load (a) : '))


def grade_of_service(s, a):
    if s == 0:
        return 1
    else:
        result = float((a * grade_of_service(s-1, a)/(s + a * grade_of_service(s-1, a))))
        print(result)
        return result


print(grade_of_service(lines, load))

Thanks in advance.

Upvotes: 0

Views: 78

Answers (1)

José M
José M

Reputation: 3509

Your recursive function is exponential over s: Each recursive call multiplies by two the number of calls.

With s = 30 you have in the line 2**30 calls, which are a lot.

Usually, the way to solve this kind of problems is iterating from the bottom up or storing the intermediate results in a table to avoid recalculating them all the time, but in this case you can solve it with a variable:

lines = int(input('Give number of service lines (s): '))
load = int(input('Give the number of the traffic load (a) : '))


def grade_of_service(s, a):
    if s == 0:
        return 1
    else:
        previous_grade_of_service = grade_of_service(s-1, a)
        return float((a * previous_grade_of_service /(s + a * previous_grade_of_service)))


print(grade_of_service(lines, load))

EDIT Here's an example for the 'cached' version:

lines = int(input('Give number of service lines (s): '))
load = int(input('Give the number of the traffic load (a) : '))

cache = [None] * (lines + 1)
cache[0] = 1
def cached_grade_of_service(s, a):
    cached = cache[s]
    if cached == None:
        cached = float((a * cached_grade_of_service(s-1, a)/(s + a * cached_grade_of_service(s-1, a))))
        cache[s] = cached
    return cached

print(cached_grade_of_service(lines, load))

Upvotes: 1

Related Questions