Recursive Function Not Returning Value

Question

This code is supposed to find the sum of the digits of an integer. When I run it, the computer just processes for a while and then nothing happens

def sum_of_digits(integer):
    numlist = list(str(integer))
    if len(numlist) == 0:
        result = 0
    elif len(numlist) == 1:
        result = numlist[0]
    else:
        midPoint = len(numlist) // 2
        result = sum_of_digits(numlist[:midPoint]) + 
        sum_of_digits(numlist[midPoint:])
    print(result)
    return result


sum_of_digits(123456)

Can you fix your indentation? It looks like you are printing `result` after returning from the function. — iz_, Nov 08 '18 at 22:22
You should make clear what do you mean by `nothing happens`. e.g. No print out at all? How did you call your `sum_of_digits`? — Anthony Kong, Nov 08 '18 at 23:00
1st, instead of assigning to result, you need to return the value directly in each if condition closure. 2nd, your sum_of_digits defined to take integer as argument, but take a list as argument within the last else closure. Function needs to have consistent argument's data type — englealuze, Nov 09 '18 at 09:44

score 1 · Answer 1 · answered Nov 09 '18 at 05:15

This answer does not convert the number to a string (or other iterable) and then back to a number.

def sum_of_digits (n: int, sum = 0) -> int:
  if n < 10:
    return n + sum
  else:
    return sum_of_digits (n // 10, sum + n % 10)

print(sum_of_digits(1))      # 1
print(sum_of_digits(12))     # 3
print(sum_of_digits(123))    # 6
print(sum_of_digits(1234))   # 10
print(sum_of_digits(12345))  # 15

score 1 · Answer 2 · answered Nov 09 '18 at 09:54

1

Another simple solution without data type conversion:

def sum_of_digits(integer):
    if integer == 0:
        return 0
    else:
        return integer % 10 + sum_of_digits(integer // 10)

answered Nov 09 '18 at 09:54

englealuze

1,445
12
19

score 0 · Answer 3 · answered Nov 08 '18 at 23:12

You've horridly confused your data types. Naming something integer does not make it an integer. You're fine on the first call. Had you done any rudimentary debugging, you'd have seen the problem: you turn the integer into a list of single-character strings.

When you split the list and recur, you pass that half-list into your function as integer. When you immediately turn it into a new string with str(integer), you get a string something like "['1']", rather than a simple character digit. When you explode that into a list, you get ['[', "'", '1', ']', "'"] as numlist ... and it's a nasty infinite recursion from there.

First, make sure you have a consistent interface for your function: if nothing else, reconstitute the half-string into an integer and feed that value to your recursive call. Second, don't get overly expansive: you can simply convert the integer to a string and work on the individual digits; no need to make a list from that. Third, see this lovely debug blog for help.

Finally, you might research other solutions on line. This is a common exercise. I'm not telling you to copy the program -- but now that you've given the problem a good attempt, you can learn about the internal processing from others.

To get you moving, here's how I instrumented your code for debugging: print useful things on enter and exit, and put in a delay (sleep) so I have a chance to interrupt the program before useful info rolls off the screen.

from time import sleep

call = 0

def sum_of_digits(integer):
    global call

    call += 1
    id = call 

    print("ENTER", call, integer)

    numlist = list(str(integer))
    print("numlist", numlist)
    sleep(1)

    if len(numlist) == 0: 
        result = 0
    elif len(numlist) == 1:
        result = numlist[0]
    else:
        midPoint = len(numlist) // 2
        result = sum_of_digits(numlist[:midPoint]) + \ 
                 sum_of_digits(numlist[midPoint:])

    print("LEAVE", id, result)
    return result


test = [0, 1, 12]
for case in test:
    call = 0
    sum_of_digits(case)
    print("-------------------------")

Output:

ENTER 1 0
numlist ['0']
LEAVE 1 0
-------------------------
ENTER 1 1
numlist ['1']
LEAVE 1 1
-------------------------
ENTER 1 12
numlist ['1', '2']
ENTER 2 ['1']
numlist ['[', "'", '1', "'", ']']
ENTER 3 ['[', "'"]
numlist ['[', "'", '[', "'", ',', ' ', '"', "'", '"', ']']
ENTER 4 ['[', "'", '[', "'", ',']
numlist ['[', "'", '[', "'", ',', ' ', '"', "'", '"', ',', ' ', "'", '[', "'", ',', ' ', '"', "'", '"', ',', ' ', "'", ',', "'", ']']
^CTraceback (most recent call last):
  File "so.py", line 33, in <module>
    sum_of_digits(case)
  File "so.py", line 23, in sum_of_digits
    result = sum_of_digits(numlist[:midPoint]) + \
  File "so.py", line 23, in sum_of_digits
    result = sum_of_digits(numlist[:midPoint]) + \
  File "so.py", line 23, in sum_of_digits
    result = sum_of_digits(numlist[:midPoint]) + \
  File "so.py", line 15, in sum_of_digits
    sleep(1)
KeyboardInterrupt

score 0 · Answer 4 · answered Nov 08 '18 at 23:21

You are calling your own function inside of itself. Also when you are calling it you are giving it a list instead of an integer so are causing it to iterate over a list instead of the number that you want. You might want to use a ''.join to return a integer instead of a list.

sum_of_digits(int(''.join(numlist[:midPoint]))))

Even If you do this there is still more work needed to be done to your function and you might want to use int() declarations to make sure you are working with integers.

Also you could use something that uses a for loop which would accomplish your goal in a more efficient manner but may not be what you are looking for.

def sum_of_digits(integer):
    ans=0
    for i in str(integer):
        ans+=int(i) 
    return ans

score 0 · Answer 5 · answered Nov 08 '18 at 23:31

Even though "nothing happens" doesn't give much info, you are clearly mixing data types in a really messy way.

Your sum_of_digits function takes an integer as a parameter, calling it integer doesn't make it one, it is still upon you to make sure you are calling it with the correct parameter.

When you call it recursively with sum_of_digits(numlist[:midPoint]) and sum_of_digits(numlist[midPoint:]) you are passing a string not an integer, and that's where things go wrong, work on that.

Recursive Function Not Returning Value

5 Answers5