#!/usr/bin/env python

def getDigitalRoot(n):
    """Recursively calculates digital root of the given number

    :param n: 0 <= n <= 10^9
    :type n: integer
    :return: digital root of the given number
    :rtype: int
    """

    if n <= 9:
        return n

    (i, n) = (n, 0)

    while i > 0:
        (i, s) = divmod(i, 10)
        n += s

    return getDigitalRoot(n)

assert getDigitalRoot(65536) == 7
assert getDigitalRoot(11) == 2
assert getDigitalRoot(0) == 0