Рекурсия - методика анализа проблем.То есть вы начинаете с проблемы и думаете о том, какой может быть рекурсивная структура решения.Вы не начинаете с рекурсивной структуры, а затем пытаетесь придумать в ней свою проблему.
Другими словами, хорошо бы практиковать рекурсивный анализ, но задача, которую вы поставили перед собой -заставить решение иметь форму однопараметрической функции - это не способ сделать это.Если вы начнете созерцать глобальные или статические переменные или извлекать контекст времени выполнения, разбивая стек вызовов, у вас будет довольно хороший намек на то, что вы еще не нашли подходящий рекурсивный анализ.
Это не означает, что существуетне элегантное рекурсивное решение вашей проблемы.Есть один, но прежде чем мы перейдем к нему, мы могли бы абстрагироваться от детали проблемы, чтобы обеспечить некоторую мотивацию.
Ясно, что если у нас уже есть непрерывная структура данных в памяти, делаянепрерывная копия не является сложной задачей.Если мы не знаем, насколько он велик, мы можем сделать два обхода: один, чтобы найти его размер, после чего мы можем выделить необходимую память, и другой, чтобы сделать копию.Обе эти задачи являются простыми циклами, что является одной из форм рекурсии.
Существенная природа рекурсивного решения состоит в том, чтобы подумать о том, как перейти от проблемы к (немного) более простой или меньшей задаче.Или, чаще, небольшое количество более мелких или более простых задач.
Такова природа одной из самых классических рекурсивных задач: сортировка последовательности чисел.Основная структура: разделите последовательность на две примерно равные части;отсортируйте каждую часть (рекурсивный шаг) и соедините результаты вместе, чтобы комбинация была отсортирована.Этот базовый план имеет по крайней мере два интересных (и очень разных) проявления:
Разделите последовательность произвольно на две почти равные части, поместив альтернативные элементы в альтернативные части или поместив первую половинув одной части, а остальные в другой части.(Первый будет хорошо работать, если мы не будем заранее знать, насколько велика последовательность.) Чтобы собрать отсортированные части вместе, мы должны чередовать («объединять»).(Это сортировка слиянием).
Разделите последовательность на два диапазона путем оценки среднего значения и помещения всех меньших значений в одну часть, а всех больших значений - в другую часть.Чтобы собрать отсортированные части, мы просто объединяем их.(Это быстрая сортировка.)
В обоих случаях нам также необходимо использовать тот факт, что одноэлементная последовательность (тривиально) отсортирована, поэтому больше не требуется никакой обработки.Если мы достаточно часто разделяем последовательность на две части, гарантируя, что ни одна часть не пуста, мы должны в конечном итоге достичь части, содержащей один элемент.(Если нам удастся точно выполнить деление, это произойдет довольно скоро.)
Интересно реализовать эти две стратегии с использованием односвязных списков, так что длины на самом деле не так легко узнать.Оба могут быть реализованы таким образом, и реализации раскрывают что-то важное о природе сортировки.
Но давайте вернемся к гораздо более простой проблеме - копированию последовательности во вновь распределенный непрерывный массив.Чтобы сделать задачу более интересной, мы не будем предполагать, что последовательность уже сохранена непрерывно, или что мы можем пройти ее дважды.
Для начала нам нужно найти длину последовательности, которую мы можемсделать, наблюдая, что пустая последовательность имеет нулевую длину, и любая другая последовательность имеет еще один элемент, чем подпоследовательность, начинающаяся после первого элемента («хвоста» последовательности.)
Length(seq):
If seq is empty, return 0.
Else, return 1 + Length(Tail(seq))
Теперь предположим, что мы выделили хранилище для копии.Теперь мы можем копировать, наблюдая, что пустая последовательность полностью скопирована, и любую другую последовательность можно скопировать, поместив первый элемент в выделенное хранилище и затем скопировав хвост последовательности в хранилище, начиная со второй позиции: (иэта процедура логически принимает два аргумента)
Copy(destination, seq):
If seq is not empty:
Put Head(seq) into the location destination
Call Copy (destination+1, Tail(seq))
Но мы не можем просто соединить эти две процедуры, потому что это будет пересекать последовательность дважды, что, как мы сказали, мы не можем сделать.Поэтому нам нужно как-то вложить эти алгоритмы.
Чтобы сделать это, мы должны начать с передачи накопленной длины через рекурсию, чтобы мы могли использовать ее для выделения памяти, когда мы знаем, насколько велик объект,Затем на обратном пути нам нужно скопировать элемент, который мы посчитали на пути вниз:
Copy(seq, length):
If seq is not empty:
Set item to its first element (that is, Head(seq))
Set destination to Copy(Tail(seq), length + 1)
Store item at location destination - 1
Return destination - 1
Otherwise: (seq is empty)
Set destination to Allocate(length)
# (see important note below)
Return destination + length
Чтобы правильно запустить рекурсию, нам нужно передать 0 в качестве начальной длины.Неправильно заставлять пользователя вставлять «магические числа», поэтому обычно мы оборачиваем функцию драйвером с одним аргументом:
Strdup(seq):
Return Copy (seq, 0)
Важное примечание : если бы это было написанов C, используя строки, нам нужно NUL-завершить копию.Это означает выделение length+1 байтов вместо length, а затем сохранение 0 в destination+length.