Recursion is a function that solves a problem by calling itself on a smaller version of the same problem. It is the tool behind every tree and graph algorithm in this phase, so we warm up with a problem you could also solve with a loop.
Given a non-negative integer n, return the sum of its decimal digits. Write it recursively (no loops, no converting to a string): peel off one digit and let a recursive call handle the remaining digits.
Examples
Input: n = 1234
Output: 10
Explanation: 1 + 2 + 3 + 4 = 10
Input: n = 0
Output: 0
Input: n = 907
Output: 16
Constraints
0 <= n <= 10**18
Goals
- Identify the base case that stops a recursion
- Express a problem as one step plus a smaller copy of itself
- Use // and % to split an integer into its last digit and the rest