文字列を逆順（再帰）｜コードで実践

文字列を逆順（再帰）

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

reverseString の計算量は素朴な実装で O(n^2) です

hello を逆順にすると olleh になります

文字列 s の逆順 reverseString(s) は、次のように再帰的に定義できます

文字列を逆順とは

reverseString(s) を再帰で書く。文字列を 先頭 + 残り に分け、残りの逆順 + 先頭 で組み立てる。

hello を逆順にすると olleh になります。s[::-1] (Python) や s.split('').reverse().join('') (JavaScript) を使えばワンライナーですが、本レッスンでは 再帰 で書きます。配列の合計と似た発想で、文字列を 先頭 1 文字 + 残り に分けて、残りの逆順 + 先頭 を組み立てる、というロジックです。

文字列を 先頭 + 残り で見るのは、再帰 を書くときの基本。配列の合計 でも同じ考え方を使った。

数学的な定義

文字列 s の逆順 reverseString(s) は、次のように再帰的に定義できます。

reverseString("") = "" (空文字列の逆順は空文字列)
reverseString(s) = reverseString(s[1:]) + s[0]

空文字列が 基底ケース、それ以外は 残りの逆順 の後ろに 先頭の 1 文字 を付ける、という形です。

Python の実装

Python

def reverseString(s):
    if len(s) == 0:
        return ""
    return reverseString(s[1:]) + s[0]

if len(s) == 0 が 基底ケース、reverseString(s[1:]) + s[0] が 再帰ケース です。s[1:] で 2 番目以降、s[0] で先頭 1 文字を取り出しています。

再帰の展開を Mermaid で見る

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

diagram (will load when visible)

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

空文字列 まで降りたら "" を返し、そこから c cb cba と組み立てながら戻ってきます

空文字列 まで降りたら "" を返し、そこから c cb cba と組み立てながら戻ってきます。abc の逆順が cba という結果が得られます。

JavaScript / Java での書き方

JavaScript

function reverseString(s) {
  if (s.length === 0) return "";
  return reverseString(s.slice(1)) + s[0];
}

JavaScript では s.slice(1) で 2 番目以降、s[0] (または s.charAt(0)) で先頭 1 文字を取れます。

Java

public class Solution {
    public static String reverseString(String s) {
        if (s.length() == 0) return "";
        return reverseString(s.substring(1)) + s.charAt(0);
    }
}

Java では s.substring(1) がスライス、s.charAt(0) が先頭文字です。文字列の連結は + でできます。

計算量とパフォーマンス

reverseString の計算量は素朴な実装で O(n^2) です。s.slice(1) や substring(1) が毎回 O(n) の文字列コピーを作るためです。実用上は O(n) の 2 ポインタ 法や、Python の s[::-1] が選ばれます。

再帰版は 読みやすさ のためのデモ実装。本番では O(n) の方法を使う。

よくある間違い

return s[0] + reverseString(s[1:]) と書いてしまうと、元の順序 のまま返ってしまう。残りの逆順 が 先 に来る、と覚える。
Java で + 演算子による文字列連結を使うと、内部で StringBuilder が走る。再帰で大量に呼ぶと遅くなるので、本番では StringBuilder 直接利用 + for ループの方がよい。
空文字列の扱いを忘れる。if len(s) == 0 を書かないと無限再帰になる。

やってみよう

下の coding 課題で、reverseString(s) を再帰で実装してください。テストでは "hello" "a" "" "abcdef" などで、文字列が正しく逆順になっているかを確認します。組み込みの reverse や [::-1] は使わず、必ず再帰で書いてください。

文字列を逆順にする問題は、回文判定 スタック 2 ポインタ の前哨戦。再帰で書けるようになれば、スタック を使った反復実装にも応用できる。

別解: 末尾を取り出す版

本レッスンでは 先頭 + 残り の形で書きましたが、逆に 末尾の 1 文字 + 残り(先頭〜末尾の 1 つ前)の逆順 で書くこともできます。

Python

def reverseString(s):
    if len(s) == 0:
        return ""
    return s[-1] + reverseString(s[:-1])

s[-1] で末尾の 1 文字、s[:-1] で末尾以外の全部を取り出します。この書き方だと、最初に末尾の文字が来るので 自然な順序で結果を組み立てる 形になります。どちらの書き方でも O(n^2) で動くので、本番性能は同じです。

配列とリストでの応用

reverseString と同じパターンで、配列の逆順 (reverseArray) も書けます。

Python

def reverseArray(arr):
    if len(arr) == 0:
        return []
    return reverseArray(arr[1:]) + [arr[0]]

文字列とほぼ同じコードで、+ が リストの連結、[arr[0]] が 1 要素のリスト という違いがあるだけ。再帰 の構造は、データ型を超えて使える、ということが分かります。スタック を使った反復実装も同じ発想で、pop して push back を繰り返すと逆順になります。これは第 4 章 (データ構造) で扱う スタック 応用の典型例なので、覚えておくと後の章で役立ちます。

よくある質問

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) に劇的に高速化します。

次のレッスン

次は ユークリッドの互除法（GCD） で、2 つの整数の最大公約数を再帰で求める方法を学びます。

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

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

理解度チェック (30 秒)

Q. 文字列の逆順とは何か、1 文で説明してください。

この章のポイント

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

関連レッスン

文字列を逆順（再帰）