Как в этом примере достигается база рекурсии?

Question

[Vladislav Shulkevich]

У Седжвика есть в домашних задачах такой пример:

public static String mystery(String s)
{
int N = s.length();
if (N <= 1) return s;
String a = s.substring(0, N/2);
String b = s.substring(N/2, N);
return mystery(b) + mystery(a);
}

Этот метод переворачивает строку. Объясните далёкому от рекурсивных методов, как тут достигается база рекурсии?

Answer 1

[Aracon]

Этот метод делит строку пополам и переставляет местами половины. Во внутренние вызовы передаются уже половины строк. Деление пополам конечно - в какой-то момент фрагмент строки будет длины 1 или 0. Чтобы обратить строку единичной длины или пустую строку, ничего делать не нужно, поэтому, если длина строки <=1, возвращается та же самая строка, - так достигается база.

Пример. В качестве символов для удобства возьмём цифры.
1) Данные уходят в глубь рекурсивных вызовов:
(12345)
((12) (345))
(((1) (2)) ((3) (45)))
Когда функция получает строку длины 1, то возвращает её же. А строка "45" уйдёт ещё на один шаг вглубь. Тем временем в вызовах, получивших обратно данные, результаты переставляются местами и возвращается получившаяся строка:
((21) ((3) ((4) (5))))
((21) ((3) (54)))
((21) (543))
(54321)

Comments

[Vladislav Shulkevich]

Круть!

[Aracon]

Vladislav Shulkevich: Спасибо)
На всякий случай ещё добавлю (чтобы не ввести в заблуждение тех, кто будет читать этот ответ), что на самом деле, конечно, вызовы в разных ветках выполняются не параллельно, как это написано выше, - я так написал для объяснения идеи.
Реально выполнение программы сперва уйдёт вглубь самой левой ветки, пока не получит значение "21", потом пойдёт в правую ветку переворачивать "345", ну и так далее. Просто в этом примере это не принципиально, но в других задачах (например, обход графа) нужно это понимать.