Traceback (most recent call last):
File "digits.py", line 8, in <module>
print(digit_sum(-45))
~~~~~~~~~^^^^^
File "digits.py", line 5, in digit_sum
return n % 10 + digit_sum(n // 10)
~~~~~~~~~^^^^^^^^^
File "digits.py", line 5, in digit_sum
return n % 10 + digit_sum(n // 10)
~~~~~~~~~^^^^^^^^^
File "digits.py", line 5, in digit_sum
return n % 10 + digit_sum(n // 10)
~~~~~~~~~^^^^^^^^^
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceededA countdown that steps by two. It works for even numbers and never stops for odd ones, and the traceback would look just like the one above.
def count_down(n):
if n == 0:
return "done"
return count_down(n - 2)
print(count_down(4)) # done (4, 2, 0)
print(count_down(5)) # 5, 3, 1, -1, -3 ... never 0
# RecursionError: maximum recursion depth exceeded
- One frame, a thousand times
When the traceback is the same line over and over, the function is not failing somewhere new each time. It is calling itself without end, and Python stops it at about a thousand levels.
- Follow the argument, not the code
Write down the value passed on each call: 5, 3, 1, -1. By the fourth call it has stepped past the base case, and every call after that moves away from it.
- A base case has to be reachable
if n == 0 is only a stopping point if every input eventually lands exactly on 0. n <= 0 would be safer here; for the exercise, the input needs changing so it can land at all.
Work out -45 // 10 by hand, then that answer // 10, then once more. Does it ever get to 0?
Floor division rounds down, towards minus infinity, so -45 // 10 is -5 and -1 // 10 is -1 again. Negative numbers never reach the base case.
The sign is not a digit, so take it away before recursing: work with abs(n). Do it once, at the start, so % 10 sees a positive number as well.
def digit_sum(n): n = ____(n) if n < 10: return ____ return n % 10 + digit_sum(n // ____)
def digit_sum(n):
"""Add up the digits of a whole number: 472 -> 13."""
n = abs(n)
if n < 10:
return n
return n % 10 + digit_sum(n // 10)
Every call after the first is given a non-negative number, so n // 10 shrinks towards 0 every time and the recursion ends. Removing the sign is also what the contract means by 'the sign is not a digit'.
Python’s % takes the sign of the divisor, so -7 % 10 is 3. Taking abs only inside the recursive call leaves that first % working on a negative number, and -7 comes out as 3.
A single digit is its own digit sum, so stopping there saves a call and covers 0 as well. It also fails safe: any value below 10, however it got there, stops the recursion.
sum(int(d) for d in str(abs(n))) does the same in one line and never recurses. Write the recursive version to understand recursion; in everyday code the string version is easier to read and has no depth limit.
- Repeat until one digit is left (the digital root), and find the one-line formula that gives the same answer.
- Write it with a while loop and no recursion.
- Count how many calls the recursive version makes for a number with d digits.