Maximum Reccursion Dept error while making a strong nummber program

Question

i am given a question to make a program which will find the next strong number if the current number is not strong number but i get maximum depth error.

my code

def solution(n):
    m = str(n)
    dig = map(int, m)
    digits = list(dig)
    sum = 0
    factorial = 1
    for i in digits:
        if i == 0:
            sum += 1
        else:
            for i in range(1, i + 1):
                factorial = factorial*i
            sum += factorial
     
    if sum == n:
        return sum
    elif sum != n:
        solution(n + 1)

print(solution(140))

Answer 1

Your problem is that you are using a recursive function. Python only allows for so many recursions. You can use a loop instead:

def solution(n):
    while True:
        m = str(n)
        dig = map(int, m)
        digits = list(dig)
        mysum = 0
        factorial = 1
        for i in digits:
            if i == 0:
                mysum += 1
            else:
                for i in range(1, i + 1):
                    factorial = factorial*i
                mysum += factorial
     
        if mysum == n:
            return mysum
        elif mysum != n:
            mysum = 0
            n = n + 1

print(solution(140))

After fixing the other bugs in your code it looks like this:

def solution(n):
    while True:
        m = str(n)
        dig = map(int, m)
        digits = list(dig)
        mysum = 0
        for i in digits:
            factorial = 1 # Needs to be set to 1 for every iteration
            if i == 0:
                mysum += 1
            else:
                for x in range(1, i+1):
                    factorial = factorial * x
                mysum += factorial 

        if mysum == n:
            return mysum
        elif mysum != n:
            mysum = 0
            n = n + 1

print(solution(140)) # prints 145
print(solution(146)) # prints 40585

Also don't use sum as a variable name as it is a builtin function.

Answer 2

Following corrections allows posted code to run

1. factorial has to be reset to 1 at the beginning of loop for factorial computation
2. Don't use variable names that's the same as popular builtin functions (i.e. sum)
3. To allow the function to be recursive we must perform Tail Call Optimization, otherwise, we quickly overcome the Python stack frame limit.
4. Python doesn't provide tail call optimization out of the box, but it's easily implemented using method from Tail Recursion In Python
5. Return the value of the recursive call i.e. solution(n +1) does not return a value

Corrections highlighted in code.

Code

 #-------------------------------------------------------
 # Decorator class to allow for optimized tail recursion
 #-------------------------------------------------------
 class Recurse(Exception):
    def __init__(self, *args, **kwargs):
        self.args = args
        self.kwargs = kwargs

def recurse(*args, **kwargs):
    raise Recurse(*args, **kwargs)
        
def tail_recursive(f):
    def decorated(*args, **kwargs):
        while True:
            try:
                return f(*args, **kwargs)
            except Recurse as r:
                args = r.args
                kwargs = r.kwargs
                continue
    return decorated

 #-------------------------------------------------------
 # Corrected code and revised to use tail call optimization
 #-------------------------------------------------------
@tail_recursive
def solution(n):
    m = str(n)
    dig = map(int, m)
    digits = list(dig)
    sum_ = 0                         # Correction: don't use sum as a variable name since it's a built-ini
    
    for i in digits:
        if i == 0:
            sum_ += 1
        else:
            # Factorial of digit i
            factorial = 1              # Correction: Reset value to 1
            for i in range(1, i + 1):
                factorial = factorial*i
            sum_ += factorial
     
    if sum_ == n:
        return sum_
    elif sum_ != n:
        # Recursive call using recurse which provides tail call optimization
        return recurse(n + 1)        

Tests

for n in range(140, 150):
    print(f'n = {n}, next strong number: {solution(n)}')

Output

n = 140, next strong number: 145
n = 141, next strong number: 145
n = 142, next strong number: 145
n = 143, next strong number: 145
n = 144, next strong number: 145
n = 145, next strong number: 145
n = 146, next strong number: 40585
n = 147, next strong number: 40585
n = 148, next strong number: 40585
n = 149, next strong number: 40585