Как рекурсивно реверсировать массив в языке C
В этом руководстве мы хотим рекурсивно закодировать функцию инверсии массива. Получается, что рекурсивный метод сложнее по сравнению с итерационным, но рекурсивная программа более формальна.
Для начала нужно определить случаи рекурсии. Для начала нужно написать программу итерационного метода, чтобы понять.
На этом рисунке в три шага объясняется операция перестановки между i и n-i, Операцию повторяют до тех пор, пока не будет достигнута половина длины картины. Мы должны повторить операцию только с первой половиной массива, иначе мы поменяем местами элементы второй половины с элементами первой половины, которые уже были обработаны, и там мы вернемся к нашему исходному массиву.
Следующий код меняет местами массив с помощью итеративного метода:
Для начала нужно определить случаи рекурсии. Для начала нужно написать программу итерационного метода, чтобы понять.
На этом рисунке в три шага объясняется операция перестановки между i и n-i, Операцию повторяют до тех пор, пока не будет достигнута половина длины картины. Мы должны повторить операцию только с первой половиной массива, иначе мы поменяем местами элементы второй половины с элементами первой половины, которые уже были обработаны, и там мы вернемся к нашему исходному массиву.
Следующий код меняет местами массив с помощью итеративного метода:
#include< conio.h>Выполнение этого кода дает:
#include< stdio.h>
int main()
{
int i,n,temp;
printf("Размер массива ");
scanf("%d",& n);
int t[n];
for(i=0; Я< n; i++)
{
printf("t[%d]=",i);
scanf("%d",& t[i]);
}
i=0;
while(i< n/2)
{
temp = t[i];
//n-1, потому что массив начинается с 0
t[i]=t[n-1-i];
t[n-1-i]=temp;
i++;
}
printf("\nОбратная таблица: \n");
for(i=0; Я< n; i++)
{
printf("\nt[%d]=%d",i,t[i]);
}
getch();
}
Инвертировать массив на C с помощью рекурсивного метода
Теперь, когда у нас есть программа для итерационного метода, мы создадим формальную версию. Вы зададитесь вопросом, чем он отличается? Колодец! Рекурсивная версия — это функция, которая вызывает саму себя до тех пор, пока не достигнет точки опоры. Этот рекурсивный вызов эквивалентен циклу в итеративной версии.
Чтобы получить рекурсивную программу, нужно только перевести итеративную программу. Точка опоры — это условие остановки в цикле whilei< n/2 (в программе ставим i>=(n+1)/2 т.к. при вызове функции размер массива n-1 уменьшался). i становится основным параметром функции, так как стоп-тест выполняется после каждого приращения i.
Чтобы получить рекурсивную программу, нужно только перевести итеративную программу. Точка опоры — это условие остановки в цикле whilei< n/2 (в программе ставим i>=(n+1)/2 т.к. при вызове функции размер массива n-1 уменьшался). i становится основным параметром функции, так как стоп-тест выполняется после каждого приращения i.
В следующем примере показано, как рекурсивно инвертировать элементы массива в C.
#include< conio.h>
#include< stdio.h>
int* inverse(int[],int,int);
main()
{
int i,n;
printf("Размер массива");
scanf("%d",& n);
int t[n];
int *ti;
for(i=0; Я< n; i++)
{
printf("t[%d]=",i);
scanf("%d",& t[i]);
}
ti=inverse(t,n-1,0);
printf("\nобратный массив: \n");
for(i=0; Я< n; i++)
{
printf("\nt[%d]=%d",i,ti[i]);
}
getch();
}
int* inverse(int t[],int n, int i)
{
int temp;
if(i>=(n+1)/2 )
return t;
else{
temp = t[i];
t[i]=t[n-i];
t[n-i]=temp;
обратная доходность (t,n,i+1);
}
}
divКомпиляция и выполнение этого кода приводит к следующему:
