Sum of digits
Answer a tiny case directly, and hand everything else to a smaller call. About 8 minutes.
A function may call itself
The digits of 4729 add up to 9 plus the digits of 472, and 472 is the same kind of question, just smaller. Like Russian nesting dolls, each doll contains a smaller copy of itself. So the answer for the whole number is the last digit plus the answer for the rest.
A function that calls itself like this is recursive. Trust the smaller call to return the right answer, and add your part.
sum_digits(4729): keep the last digit 9, and ask sum_digits(472).
Every recursion needs a base case
If the function always called itself, it would never stop, like a dream inside a dream inside a dream. So pick a case small enough to answer directly: a number with one digit is its own digit sum.
Check it first, before the smaller call. Each call must also move closer to the base case, or the calls never end.
def sum_digits(n):
if n < 10:
return n
return n % 10 + sum_digits(n // 10)sum_digits(305) returns 5 + sum_digits(30). What does sum_digits(30) do?
- AReturns 0 + sum_digits(3)
- BReturns 3 + sum_digits(0)
- CStops, because 30 ends in 0
Show the answer
Returns 0 + sum_digits(3). 30 isn't below 10, so it keeps its last digit 0 and calls sum_digits(3), a base case. The total is 5 + 0 + 3 = 8.
Sum of digits
Return the sum of the digits of n. Use recursion: answer a one-digit n directly, and let a smaller call handle the rest.
n = 4729 → 22
0 ≤ n ≤ 2,000,000,000 · at most 10 digits, so at most 10 calls deep