694. Sum of Digits of a Number

Given a non-negative integer N, return the sum of all its digits using recursion. For example, for N = 1234, the digit sum is 1+2+3+4 = 10. The function should extract the last digit at each recursive step.

Input: A single non-negative integer N (0 ≤ N ≤ 10^18).

Output: A single integer — the sum of digits of N.

Examples

Input: 1234
Output: 10
Explanation: 1+2+3+4=10. Recursion: digitSum(1234)=4+digitSum(123)=4+3+digitSum(12)=4+3+2+digitSum(1)=4+3+2+1=10.

Input: 0
Output: 0
Explanation: Single digit 0, sum is 0.

Input: 9999
Output: 36
Explanation: 9+9+9+9=36.

Constraints

• 0 <= N <= 10^18

Asked by