Sum of Digits of a Number

Given a non-negative integer N, compute the sum of its decimal digits using a recursive function. For example, the digit sum of 12345 is 1+2+3+4+5 = 15. Implement the digit-sum computation recursively rather than iteratively.

Input: A single line containing one non-negative integer N (may have up to 19 digits, so read it as a 64-bit integer). Output: A single line containing the sum of the decimal digits of N.

0 <= N <= 10^18

This is a great template for 'peel one piece off a number/string/list, recurse on the rest, combine results' - a shape that reappears throughout this entire category (reversing a string, checking a palindrome, and more).

Compute the sum of a number's digits using a recursive function instead of a loop. Brute force: Compute the digit sum with a simple iterative loop using the same N%10/N/10 extraction - equally efficient, but this problem specifically asks for the recursive framing to practice expressing a numeric peeling process as recursion. Optimised: Recognizing that 'sum of digits of N' can be expressed as 'last digit of N, plus sum of digits of everything before it' directly mirrors how you'd naturally break down the problem by hand - each recursive call peels off exactly one digit, reducing N until it reaches the base case of 0.

1. The BASE CASE: digitSum(0) = 0. 2. The RECURSIVE CASE: the last digit of N is N % 10, and the remaining digits form N / 10 - so digitSum(N) = N % 10 + digitSum(N / 10). 3. Each call peels off one digit and adds it to the result of the smaller recursive call on the rest.

Time: O(log N) - the number of recursive calls equals the number of digits in N. Space: O(log N), for the recursion call stack (one frame per digit).

N = 0 must output 0. The maximum N (10^18) has 19 digits and must be read as a long, not an int.

Be ready to note that this recursion depth is bounded by the NUMBER OF DIGITS (very small, even for N up to 10^18), not by N itself - a useful distinction when reasoning about recursion depth and potential stack overflow risk.