桁数を数える（再帰）
1234 は 4 桁、7 は 1 桁。文字列に変換して長さを数えればすぐですが、ここでは数のまま再帰で数えます。使うのは「10 で割ると桁が 1 つ落ちる」という性質だけです。
10 で割っているのに、0 にならない
123 を 10 で割ると 12、もう一度割ると 1。あと 1 回で 0 になりそうです。ところが次の関数は止まりません。
Python
def drop(n):
if n == 0:
return
print(n)
drop(n / 10) # 割り算が小数を返しているPython の / は小数を返すので、123 は 12.3, 1.23, 0.123, 0.0123 と小さくなり続け、いつまでも 0 ちょうどにはなりません。JavaScript の / も同じです。
桁を落としたいときは、小数点以下を切り捨てる割り算を使います。Python は //、JavaScript は Math.floor(n / 10)。Java と Go は整数どうしの / がもともと切り捨てなので、そのままで大丈夫です。
Python
def drop(n):
if n == 0:
return
print(n % 10) # 一番下の桁
drop(n // 10) # 残りの桁n % 10 で一の位、n // 10 で残り。この 2 つが、数を桁ごとに扱うときの道具です。drop(1234) を動かすと、こう進みます。
プレーンテキスト
1234 一の位は 4 残りは 123
123 一の位は 3 残りは 12
12 一の位は 2 残りは 1
1 一の位は 1 残りは 0 -> ここで止まる4 回で 0 に着きました。1234 が 4 桁であることと、降りた段数が一致しています。
割って縮む再帰は、すぐ終わる
1 ずつ減らす再帰は、n が 100 万なら 100 万段降ります。10 で割る再帰は、100 万でも 7 段で終わります。桁の数だけしか降りないからです。19 桁の巨大な数でも 19 段です。
引く再帰と割る再帰では、深さの増え方がまるで違います。引く再帰は入力が 10 倍になれば深さも 10 倍ですが、割る再帰は入力が 10 倍になっても深さは 1 段しか増えません。割って縮める再帰は、驚くほど浅いところで止まります。この性質は、このあとの探索でもそのまま効いてきます。
0 だけは、話が違う
止める位置を「0 になったら」にすると、0 そのものを渡されたときに困ります。0 は 1 桁として数えたいのに、いきなり止まって 0 桁と答えてしまうからです。
9 を渡したときも同じで、9 // 10 は 0 なので、0 で止める形だと 1 段余計に降りて 2 桁と答えます。1 桁まで来た時点で止める、と決めておけば、0 も 9 も同じ扱いで済みます。テストの先頭 2 件がまさにこの 0 と 9 なので、ここを外すと最初から落ちます。
要件
- 関数
countDigits(n)を実装し、桁数を整数で返す - for / while / 文字列変換 (str / String) を使わず、必ず再帰で実装する
- 基底ケースは n < 10 のとき 1 を返す
入出力例
countDigits(0) → 1
countDigits(9) → 1
countDigits(10) → 2
countDigits(123) → 3
countDigits(9999) → 4
countDigits(123456) → 6ヒント
