文字列を逆順（再帰）

hello を olleh にします。組み込みの reverse を使えば一発ですが、ここでは文字列を「先頭 1 文字」と「残り」に分けて再帰で扱います。配列のときと道具は似ていますが、境界の間違え方が違います。

1 文字ずれるだけで、止まらなくなる

文字列を 1 文字ずつ縦に表示する関数です。

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 なら末尾側からも同じように取り出せます。

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 文字ずつ短くなることに変わりはないので、再帰はきちんと止まります。違ってくるのは、戻ってくるときに結果が組み上がる順番のほうです。先頭から削るか末尾から削るかを先に決めてから書き始めると、途中で混乱しません。

どちらで書いても、文字列を切り出すたびに新しい文字列が作られます。短い入力なら気になりませんが、これが積み重なると効いてくる、ということだけ頭の隅に置いておいてください。

演習で使う書き方

本文の showChars は先頭から表示します。逆順を返す演習では、残りの処理が戻るのを待ってから先頭をつなぎます。文字列の + は連結で、"青" + "空" は "青空" です。停止条件も連結する再帰の一歩も自分で書きます。

1. 空文字列での停止と、残りの逆順への再帰を自分で実装する
2. 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える