Kode Program (Python)

def jumlah_digit_iteratif(n):
   jum = 0
   while (n > 0 or jum > 9):
       if (n == 0):
           n = jum
           jum = 0
       jum += n % 10
       n //= 10
   return jum

def jumlah_digit_rekursif(n):
   if (n < 10): return n
   jum = jumlah_digit_rekursif(n // 10)
   n %= 10
   return jumlah_digit_rekursif(jum + n)

def jumlah_digit(n):
   return 0 if (n == 0) else (
       9 if (n % 9) == 0 else n % 9
   )
   # Ekuivalen dengan:
   # if (n == 0): return 0
   # if (n % 9 == 0): return 9
   # else return (n % 9)

### Program Utama
if __name__ == '__main__':
   n = int(input('\nMasukkan sebuah bilangan asli: '))
   print(f'=> jumlah_digit_iteratif({n}) = {jumlah_digit_iteratif(n)}')
   print(f'=> jumlah_digit_rekursif({n}) = {jumlah_digit_rekursif(n)}')
   print(f'=> jumlah_digit({n}) = {jumlah_digit(n)}')
### Akhir Program Utama
__________________

Pembahasan

Untuk menghitung jumlah digit dari sebuah bilangan secara berulang sampai jumlah digitnya merupakan bilangan satuan, kita bisa melakukan 3 pendekatan.

Pendekatan 1: Brute-force

Pendekatan brute-force dilakukan berdasarkan "cara manual" kita menghitung.

Misalnya, diberikan bilangan 12345. Langkah penghitungan:

• 1+2+3+4+5 = 15
• 1+5 = 6

Untuk pendekatan ini, setidaknya terdapat 2 metode untuk pendekatan ini, yaitu metode iteratifdanrekursif.

Algoritma dengan metode iteratif (parameter: n)

1. Inisialisasi: jum = 0
2. Looping:
   Selama n > 0 atau jum > 9, lakukan:
      Jika n = 0, maka:
          n = jum
          jum = 0
      jum = jum + n mod 10
      n = n div 10
3. Kembalikan nilai jum

Algoritma dengan metode rekursif (parameter: n)

1. Jika n < 10, kembalikan nilai n.
2. Jika tidak:
      jum = jumlah digit dari (n div 10)
      n = n mod 10
      Kembalikan jumlah digit dari (jum + n)

Pendekatan 2: Dengan prinsip keterbagian oleh 9

Semua bilangan bulat n dapat direpresentasikan dengan:
n = 9x + k, dengan x, k ∈ ℤ.

• Jika n kelipatan 9, maka k = 0, jumlah digit secara berulang hingga jumlah digitnya merupakan bilangan satuan pasti sama dengan 9.
• Sedangkan jika n bukan kelipatan 9, maka k ≠ 0, jumlah digit secara berulang hingga jumlah digitnya merupakan bilangan satuan sama dengan k.

Maka, kita dapat mengkonstruksi sebuah algoritma yang lebih elegan dibanding dua algoritma pada pendekatan 1 di atas, dengan kompleksitas waktu yang lebih singkat dan sederhana.

Algoritma

1. Jika n = 0, maka kembalikan 0.
2. Jika n mod 9 = 0, maka kembalikan 9.
   Jika tidak, maka kembalikan n mod 9.

__________________

Ketiga algoritma tersebut diimplementasikan pada program di atas. Mau menggunakan yang mana, silahkan pilih. Dari sudut pandang kompleksitas waktu, algoritma terakhir adalah yang paling efisien.

Contoh hasil eksekusi dapat dilihat pada gambar.