桁数を数える（再帰）｜コードで実践

桁数を数える（再帰）

このレッスンで分かること

countDigits の計算量は O(log10 n) です

123 の桁数は 3、7 の桁数は 1、9876 の桁数は 4 です

整数 n (n >= 0) の桁数 countDigits(n) は、次のように再帰的に定義できます

桁数を数えるとは

整数 n の桁数を再帰で求める。n / 10 で問題を小さくする発想を体感する。本レッスンでは、桁数を数えるの基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

123 の桁数は 3、7 の桁数は 1、9876 の桁数は 4 です。re モジュールや len(str(n)) を使えば一発ですが、本レッスンでは敢えて 再帰 で書いてみます。これは「整数を 1 桁減らす には 10 で割る (整数除算)」という発想を体に染み込ませる、いい練習になります。

123 / 10 = 12、12 / 10 = 1、1 / 10 = 0。10 で割る ことが 桁を 1 つ減らす 操作に対応する。

数学的な定義

整数 n (n >= 0) の桁数 countDigits(n) は、次のように再帰的に定義できます。

countDigits(0) = 1 (0 も 1 桁と数える)
countDigits(n) = 1 + countDigits(n / 10) (n >= 10 の場合)
countDigits(n) = 1 (1 <= n <= 9 の場合)

n が 1 桁になったら 1 を返し、それ以外は n / 10 (整数除算) で 1 桁小さくして再帰呼び出し、というロジックです。

Python の実装

Python では // 演算子で整数除算ができます。

Python

def countDigits(n):
    if n < 10:
        return 1
    return 1 + countDigits(n // 10)

if n < 10: return 1 が 基底ケース です。n = 0 も含めて 1 桁扱いしたいので、< (より小さい) を使うのが安全。1 + countDigits(n // 10) が 再帰ケース で、n を 10 で割って 桁を 1 つ落としています。

再帰の展開を Mermaid で見る

countDigits(1234) がどう展開されるか、Mermaid で描いてみます。

diagram (will load when visible)

図のポイント (テキスト併記)

1 まで降りたら 1 を返し、そこから 1 ずつ加算 しながら戻ってきます

1 まで降りたら 1 を返し、そこから 1 ずつ加算 しながら戻ってきます。最終的に 4 が返るのは、1234 が 4 桁 だからです。

JavaScript / Java での書き方

JavaScript

function countDigits(n) {
  if (n < 10) return 1;
  return 1 + countDigits(Math.floor(n / 10));
}

JavaScript では / で割ると 小数 が混ざるので、Math.floor で 切り捨て が必要です。これを忘れると 12.3 のような小数が紛れ込み、意図した桁数が返らなくなるため、Math.floor で整数除算を明示するのが安全です。

Java

public class Solution {
    public static int countDigits(int n) {
        if (n < 10) return 1;
        return 1 + countDigits(n / 10);
    }
}

Java では int / int は自動的に 整数除算 (切り捨て) になるので、Math.floor は不要です。

計算量

countDigits の計算量は O(log10 n) です。10 で割る たびに n が 1 桁ずつ減るので、n の桁数だけ再帰が呼ばれます。n = 10^18 は 19 桁なので 19 回しか呼ばれません。非常に高速です。

2 で割る 10 で割る のように、値を割っていく 再帰は O(log n) になる。二分探索 も同じ仲間。

よくある間違い

if n == 0: return 1 を基底にすると、9 のような 1 桁の値で countDigits(0) まで降りてしまい、結果が 2 になる (9 -> 0 -> 1 + 1)。正しくは n < 10 で止める。
JavaScript で n / 10 をそのまま渡すと小数が入る。Math.floor を忘れない。
負の数を渡された場合の挙動を考えていない。本レッスンでは n >= 0 を前提とする。

やってみよう

下の coding 課題で、countDigits(n) を再帰で実装してください。テストでは 0 9 10 123 9999 123456 などで桁数が正しく返るかを確認します。str(n) や len() などの文字列変換は使わず、必ず再帰と 10 で割る 操作で書いてください。

桁数を数える問題は、各桁の合計 (digit sum) 各桁を反転した値 (reverse number) 回文判定 などの応用問題の入り口だ。同じパターンの再帰で書ける兄弟問題が多い。

兄弟問題: 各桁の合計

countDigits と似た構造で、各桁の合計 を求める関数 digitSum も書けます。

Python

def digitSum(n):
    if n < 10:
        return n
    return (n % 10) + digitSum(n // 10)

n % 10 で n の 1 の位 (一番下の桁) を取り出し、n // 10 で残りの桁に進む、という違いだけ。countDigits では 1 + していたところを n % 10 + に変えただけ、と言えます。再帰 のパターンは似た形を取りやすい、ということがよく分かる例です。

2 進数版への発展

10 で割る 代わりに 2 で割る (n // 2) を使うと、2 進数での桁数 (= ビット長) が求まります。countDigits(n, 2) のように 基数 を引数にすると、汎用的な 桁数カウント 関数になります。これは 情報量 エントロピー ハフマン符号 などの計算で実際に使われる重要なテクニックです。

本章ではまだ 2 進数 には踏み込みませんが、再帰 で書いておけば、10 進数 でも 2 進数 でも、ロジックの本質は変わらない、ということを覚えておいてください。

よくある質問

Q. 再帰とループはどっちを使うべき？

A. ツリー構造や分割統治（merge sort, BST 走査）は再帰が自然で読みやすくなります。シンプルな反復処理はループが速くスタックも消費しません。再帰深さが配列長に比例する場合、スタックオーバーフローのリスクがあるため気をつけてください。

Q. 再帰のベースケースを忘れるとどうなる？

A. 無限再帰になりスタックオーバーフローします。最初の 1 行目に if (base) return; を書く習慣を付けると安全です。Python は sys.setrecursionlimit で上限を変えられますが、根本的にループに書き換える方が安定します。

Q. 再帰を高速化する方法は？

A. 同じ引数で再計算しているなら memoize（メモ化）で結果をキャッシュします。Python は functools.lru_cache、Java/JS は HashMap で実装します。フィボナッチを memo 付きにすると指数 O(2ⁿ) から線形 O(n) に劇的に高速化します。

次のレッスン

次は 文字列を逆順（再帰） で、整数 n の桁数を再帰で求めるを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

桁数を数えるの要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 桁数を数えるとは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

桁数を数える（再帰）