文字列を逆順（再帰）
hello を olleh にします。組み込みの reverse を使えば一発ですが、ここでは文字列を「先頭 1 文字」と「残り」に分けて再帰で扱います。配列のときと道具は似ていますが、境界の間違え方が違います。
1 文字ずれるだけで、止まらなくなる
文字列を 1 文字ずつ縦に表示する関数です。
Python
def showChars(s):
if s == "":
return
print(s[0])
showChars(s[0:])s[1:] と書くつもりが s[0:] になっています。s[0:] は「0 番目以降」、つまり元の文字列そのままです。1 文字も短くならないので止まりません。
s[1:] に直すと showChars("abc") は a, b, c と表示して終わります。JavaScript なら s.slice(1)、Java なら s.substring(1) が同じ働きをします。
切り出しの開始位置が 1 つずれるだけで、止まるか止まらないかが変わります。しかも見た目はほとんど同じなので、読み返しても気づきにくい間違いです。切り出しを書いたら、その 1 行だけを取り出して「これは何文字短くなるか」を確かめる癖をつけてください。
1 文字残して止めると、空の入力で落ちる
止める位置を「長さが 1 になったら」にしたくなることがあります。1 文字なら逆順にしても同じ、という理屈は正しいのですが、空文字列を渡されると条件を素通りして s[0] に進み、範囲外エラーになります。空文字列まで降ろしてから止めれば、1 文字でも 0 文字でも同じ道を通ります。
動作確認にも罠があります。racecar は逆順にしても racecar のままなので、これで試すと壊れていても気づけません。文字数が偶数か奇数かで挙動が変わる書き間違いもあるので、abc と abcd の両方で確かめると安心です。
末尾から取る道具もある
先頭から削るのが唯一の方法ではありません。Python なら末尾側からも同じように取り出せます。
Python
s = "abc"
s[0] # "a" 先頭 1 文字
s[1:] # "bc" 先頭以外
s[-1] # "c" 末尾 1 文字
s[:-1] # "ab" 末尾以外JavaScript なら s.slice(-1) と s.slice(0, -1)、Java なら s.charAt(s.length() - 1) と s.substring(0, s.length() - 1) が同じ役割です。
どちらの端から削っても、1 文字ずつ短くなることに変わりはないので、再帰はきちんと止まります。違ってくるのは、戻ってくるときに結果が組み上がる順番のほうです。先頭から削るか末尾から削るかを先に決めてから書き始めると、途中で混乱しません。
どちらで書いても、文字列を切り出すたびに新しい文字列が作られます。短い入力なら気になりませんが、これが積み重なると効いてくる、ということだけ頭の隅に置いておいてください。
要件
- 関数
reverseString(s)を実装し、文字列を返す - for / while / 組み込みの reverse は使わず、必ず再帰で実装する
- 基底ケース (空文字列のとき 空文字列を返す) を書く
入出力例
reverseString("hello") → "olleh"
reverseString("a") → "a"
reverseString("abcdef") → "fedcba"
reverseString("12345") → "54321"
reverseString("racecar") → "racecar"ヒント
