The coding question
Add two integers by place value: ones, then tens, then hundreds. You can only add single place values together, and you can't use loops, so use recursion.
Ask a few questions first
| Ask | What we'll assume |
|---|---|
| Can the numbers be negative? | No, both are zero or positive. |
| Can I use % and // to pull out digits? | Yes. a % 10 is the ones digit and a // 10 drops it. |
| Can I turn the numbers into strings? | We'll stick to math, but strings are a fine alternative if you say so. |
| Can the numbers have different lengths? | Yes, like 457 + 68. |
| What should it return? | The sum as an integer. |
A couple of examples
| Input | Output |
|---|---|
| add(457, 68) | 525 |
| add(999, 1) | 1000, the carry goes all the way out to a new place |
| add(0, 0) | 0 |
Start with brute force
The obvious answer is a + b, which breaks the rules. The next obvious one is a loop over digits like you'd do on paper, which also breaks the rules. So the real question is how to turn that paper loop into recursion.
Cost: the loop version is O(d), where d is the number of digits, and so is the recursive version. The difference is following the rules.
A better way
Adding on paper does the same thing at every place: add the two digits plus whatever you carried, write down the ones digit, and carry the rest. That repeated step is the recursive call. It's the same kind of thinking you use when walking trees: handle one piece, let the call handle the rest.
Each call handles the ones place of what's left, then calls itself on both numbers with their ones digit chopped off, passing the carry along. The result from that call is the higher places, so multiply it by 10 and put this place's digit in front.
Stop when both numbers are 0 and there's no carry. Forgetting the carry in the stopping rule is how 999 + 1 turns into 0.
- Base case: if a, b and carry are all 0, return 0.
- Add the ones digits and the carry: a % 10 + b % 10 + carry. This is at most 9 + 9 + 1 = 19.
- This place's digit is that sum % 10, and the new carry is that sum // 10.
- Call add on a // 10 and b // 10 with the new carry to get the higher places.
- Return this place's digit plus 10 times the higher places.
The code
def add(a, b, carry=0):
# Nothing left in either number and nothing carried: we're done.
if a == 0 and b == 0 and carry == 0:
return 0
place = a % 10 + b % 10 + carry
# Keep the ones digit here, and carry the rest into the next place.
return place % 10 + 10 * add(a // 10, b // 10, place // 10)| Cost | Why | |
|---|---|---|
| Time | O(d) | One call per digit of the longer number, plus one if there's a final carry |
| Space | O(d) | Each call waits on the stack for the one after it |
Test it
Walk through one of the examples out loud, then check the cases that tend to break things:
- Both zero: the base case returns 0 right away.
- A carry that runs off the end, like 999 + 1: the carry keeps the recursion going one extra place.
- Different lengths, like 5 + 0 or 457 + 68: the shorter number just becomes 0 and keeps adding 0s.
- Very long numbers: Python's recursion limit is about 1,000 calls, so numbers with more than about 1,000 digits would fail. Mention it.
Common mistakes
- Stopping when a and b are 0 but ignoring the carry, which drops the leading 1 in 999 + 1.
- Writing the carry as place > 9 and then adding True. It works in Python but is confusing to read. Use place // 10.
- Sneaking in a loop, like a list comprehension or sum() over the digits. Those are loops too.
- Building the answer backwards, putting the higher places in the ones spot. Check with a lopsided example like 100 + 1.
Follow-up questions
What if the interviewer says even 10 * rest is cheating?
Return the digits as a string instead: str(rest) + str(digit), with the base case returning an empty string. Then convert at the end, or keep it as a string.
How would you handle negative numbers?
If the signs match, add the sizes and keep the sign. If they differ, you need subtraction with borrowing, which is the same recursion with a borrow instead of a carry.
How would you avoid the recursion limit?
Without loops you can't fully, but you can handle several digits per call, like 3 at a time with % 1000, which cuts the depth by 3.
How the time adds up
| Minutes | What you're doing |
|---|---|
| 0–5 | Clarify the rules: what counts as a loop, negatives, return type |
| 5–10 | Show the paper method and why the plain loop isn't allowed |
| 10–20 | Turn one place's step into a recursive call with a carry |
| 20–35 | Write the code |
| 35–40 | Test 457 + 68, 999 + 1 and 0 + 0 |
| 40–45 | Follow-up questions |
Key concepts used here
We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Bloomberg.