Переворот массива: итеративно и рекурсивно

Иллюстрация разворота массива: обмен элементов по двум указателям с краёв к середине

Массив — это упорядоченная коллекция элементов, расположенных в смежных ячейках памяти. Разворот (переворот) массива — частая операция в программировании: она меняет порядок элементов на обратный. В этой статье вы научитесь реализовывать разворот массива двумя основными способами: итеративно и рекурсивно. Приведённые алгоритмы работают на массивах/списках в большинстве языков и служат базовой техникой при решении задач и на интервью.

Итеративный способ

Условие задачи

Дан массив arr. Нужно развернуть порядок элементов массива и вывести результат. Реализуйте решение с использованием циклов.

Примеры:

arr = [45, 12, 67, 63, 9, 23, 74] -> [74, 23, 9, 63, 67, 12, 45]
arr = [1, 2, 3, 4, 5, 6, 7, 8] -> [8, 7, 6, 5, 4, 3, 2, 1]

Подход (двойной указатель)

Коротко: используйте два указателя — один на начало, другой на конец — и поочерёдно меняйте соответствующие элементы местами до середины.

Пошагово:

Инициализируйте индексы i = 0 и j = size - 1.
В цикле поменяйте arr[i] и arr[j].
Увеличьте i на 1 и уменьшите j на 1.
Повторяйте, пока i < size/2 (или пока i < j).

C++: разворот с помощью циклов

// C++ program to reverse the elements of an array using loops  
#include   
using namespace std;  
  
  
void reverseArr(int arr[], int size)  
{  
 for(int i=0, j=size-1; i

Вывод:

Original Array:   
45 12 67 63 9 23 74   
Reversed array:   
74 23 9 63 67 12 45

См. также: Как развернуть строку в C++, Python и JavaScript

`Python: разворот с помощью циклов`

# Python program to reverse the elements of a list using loops  
  
def reverseList(arr, size):  
    i = 0  
    j = size-1  
    while i

Вывод совпадает с примером выше.

`JavaScript: разворот с помощью циклов`

// JavaScript program to reverse the elements of an array using loops  
function reverseArr(arr, size) {  
 for(let i=0, j=size-1; i<(size)/2; i++, j--) {  
 [arr[i], arr[j]] = [arr[j], arr[i]];  
 }  
}  
  
function printArrayElements(arr, size) {  
 for(let i=0; i

Вывод аналогичен предыдущим языкам.

`Рекурсивный способ`

`Условие задачи`

То же самое: дан массив arr — нужно развернуть элементы и вывести результат. Реализуйте решение с использованием рекурсии.

`Подход (рекурсия)`

Идея: обменять элементы на позициях start и end, затем рекурсивно развернуть подмассив между start+1 и end-1. Базовый случай — когда start >= end.

Шаги:

Инициализируйте start = 0 и end = size - 1.
Если start >= end — прекратите рекурсию.
Поменяйте местами arr[start] и arr[end].
Вызовите функцию рекурсивно с start+1 и end-1.

`C++: рекурсивная реализация`

// C++ program to reverse an array using recursion  
#include   
using namespace std;  
  
void reverseArr(int arr[], int start, int end)  
{  
 if (start >= end)  
 {  
 return;  
 }  
  
swap(arr[start], arr[end]);  
 reverseArr(arr, start+1, end-1);  
}  
  
void printArrayElements(int arr[], int size)  
{  
 for(int i=0; i

Вывод тот же, что и в итеративной версии.

`Python: рекурсивная реализация`

# Python program to reverse an array using recursion  
  
def reverseList(arr, start, end):  
    if start >= end:  
        return  
  
    arr[start], arr[end] = arr[end], arr[start]  
    reverseList(arr, start+1, end-1)  
  
def printListElements(arr, size):  
    for i in range(size):  
        print(arr[i], end=" ")  
    print()  
  
# Driver Code  
arr = [45, 12, 67, 63, 9, 23, 74]  
size = len(arr)  
  
# Printing the original array  
print("Original Array:")  
printListElements(arr, size)  
  
# Reversing the array  
reverseList(arr, 0, size-1)  
  
# Printing the reversed array  
print("Reversed Array:")  
printListElements(arr, size)

`JavaScript: рекурсивная реализация`

// JavaScript program to reverse an array using recursion  
  
function reverseArr(arr, start, end)  
{  
 if (start >= end)  
 {  
 return;  
 }  
 [arr[start], arr[end]] = [arr[end], arr[start]];  
 reverseArr(arr, start+1, end-1);  
}  
  
function printArrayElements(arr, size)  
{  
 for(let i=0; i

`Анализ сложности`

Временная сложность: O(n) — каждый элемент обрабатывается не более одного раза.
Память: O(1) дополнительной памяти для итеративного метода (in‑place). Рекурсивный метод использует стек вызовов O(n) в худшем случае (n/2 уровней рекурсии), что важно учитывать для больших массивов.

Важно: если массив очень большой, рекурсивный вариант может привести к переполнению стека (stack overflow) в языках с ограниченной глубиной стека.

`Практические советы и дополнительные варианты (набор приёмов)`

`Альтернативные подходы`

Использовать встроенные функции/методы: Python arr[::-1], list.reverse(), JavaScript arr.reverse(), C++ std::reverse(begin, end).
Создать новый массив и заполнить его элементами в обратном порядке (требует O(n) дополнительной памяти) — удобно, если нужно сохранить исходный массив.

`Когда способ не подходит (противопоказания и кейсы)`

Нельзя менять элементы in‑place, если тип элементов иммутабелен или требуется сохранять исходный массив.
В многомерных массивах «разворот» может иметь двоякий смысл: разворот внутри строк, разворот порядка строк и т.д. Ясно указывайте уровень преобразования.
Для потоковой обработки (stream) хранение всего массива может быть недопустимо — используйте буферизацию или внешнее хранение.

`Ментальная модель (heuristic)`

Думайте «двухуказательно»: один указатель с левого края, другой — с правого; они сходятся к середине, меняя элементы парами.

`Факт‑бокс: ключевые числа`

Время: O(n)
Память (in‑place): O(1)
Рекурсия: глубина ~ n/2

`Чек‑лист для собеседования (для кандидата)`

Объясните идею двух указателей устно.
Напишите код, который работает in‑place и корректно обрабатывает пустой и одноэлементный массив.
Укажите временную и пространственную сложность.
Обсудите альтернативы: встроенные методы и копирование в новый массив.
Вспомните ограничения языка (глубина стека, иммутабельность).

`Чек‑лист для интервьюера (что проверить)`

Корректность при чётной и нечётной длине.
Работа с пустым массивом и массивом из одного элемента.
Граничные случаи: большие массивы, типы элементов.
Наличие комментариев про сложность и безопасность (стек vs итерация).

`Критерии приёмки`

Алгоритм возвращает массив с элементами в обратном порядке.
Для in‑place варианта дополнительная память не используется (кроме константной).
Производительность: O(n) по времени.
Код корректно обрабатывает пустые и одноэлементные массивы.

`Примеры тестов и критерии проверки`

Пустой массив -> пустой массив.
Длина 1 -> тот же элемент.
Чётная/нечётная длина -> порядок обратный.
Массив с одинаковыми элементами -> тот же набор в обратном порядке (не меняется визуально).
Большой массив (например, >10^5) для проверки времени и, при рекурсии, риска переполнения стека.

`Небольшая шпаргалка (cheat sheet)`

Итеративно: два указателя, swap, i++, j–.
Рекурсивно: swap(start,end); recurse(start+1,end-1).
Быстрое в Python: arr[::-1] или list(reversed(arr)); JavaScript: arr.reverse(); C++: std::reverse.

`Модель принятия решения (простое дерево)`

flowchart TD
  A[Нужен in-place?] -->|Да| B{Есть риск переполнения стека?}
  A -->|Нет| C[Создать новый массив / использовать встроенный метод]
  B -->|Да| D[Использовать итеративный метод]
  B -->|Нет| E[Рекурсивный метод допустим]

`Глоссарий (1‑строчный)`

In‑place: изменение структуры данных без значимого дополнительного объёма памяти.
Swap: обмен значений между двумя позициями.
Stack overflow: переполнение стека вызовов при глубокой рекурсии.

`Краткое резюме`

Разворот массива — базовая операция, легко реализуется через два указателя или с помощью рекурсии.
Итеративный метод предпочтителен для больших массивов (O(1) дополнительной памяти).
Рекурсивный метод более выразителен, но может потребовать O(n) стековой памяти.
Всегда проверяйте пустые и граничные случаи, и помните про встроенные методы языка, если они доступны.

Если нужно, могу добавить компактную таблицу сравнения подходов, дополнительные реализации на других языках или готовый модуль/функцию для вашего проекта.

Переворот массива: итеративный и рекурсивный методы