Here is a C program to reverse an array by swapping elements and recursion. To Reverse an array we have to reverse the sequence of array elements. The first element of array should become the last element and last element will become the first element.
For Example:
If Input array is : 1 2 3 4 5 6 7
Reversed array should be : 7 6 5 4 3 2 1
To reverse an array of length N using recursion, we have to swap the leftmost(array[0]) and rightmost(array[N-1]) element of array and then recursively reverse the inner sub-array from index 1 to N-2. Keep on repeating this unless size of sub-array is greater than one.
Let inputArray is an array of length N and leftIndex and rightIndex are two integer variables to store index references
- We can use recursion to reverse an array by creating a smaller sub-problem from original problem.
- To reverse an array, we will first swap first element(inputArray[0]) and last element(inputArray[N-1]) of array and then recursively reverse subarray from index 1 to N-2.
- Let reverse is a function with takes array, leftIndex and rightIndex as input. It first swap inputArray[leftIndex] and inputArray[rightIndex] and then recursively call itself on sub array from index leftIndex+1 to rightIndex-1.
- void reverse(int *array, int leftIndex, int rightIndex);
- reverse(inputArray, i, j) = swap(inputArray[i], inputArray[j]) and reverse(inputArray, i+1, j-1).
- Recursion will break when leftIndex becomes >= rightIndex.
C program to reverse and array using recursion
Below program uses two user defined functions 'swap' and 'reverse'. Function swap(int *array, int leftIndex, int rightIndex) swaps the elements of array at index leftIndex and rightIndex whereas function reverse(int *array, int leftIndex, int rightIndex) is a recursive function that reverse the sub array of array from index leftIndex to rightIndex.
Reverse function internally calls swap function to swap leftmost and rightmost element of subarray and then all itself to reverse sub-array excluding leftmost and rightmost element. Recursion will terminate when leftIndex becomes greater than or equal to rightIndex, or in other words when size of the sub-array becomes less than or equal to 1.
#include <stdio.h>
void swap(int *array, int leftIndex, int rightIndex);
void reverse(int *array, int leftIndex, int rightIndex);
int main(){
int inputArray[500], elementCount, counter;
printf("Enter number of elements in array: ");
scanf("%d", &elementCount);
printf("Enter %d numbers \n", elementCount);
for(counter = 0; counter < elementCount; counter++){
scanf("%d", &inputArray[counter]);
}
reverse(inputArray, 0, elementCount - 1);
printf("Reversed Array\n");
for(counter = 0; counter < elementCount; counter++){
printf("%d ", inputArray[counter]);
}
return 0;
}
void swap(int *array, int leftIndex, int rightIndex){
int temp;
temp = array[leftIndex];
array[leftIndex] = array[rightIndex];
array[rightIndex] = temp;
}
void reverse(int *array, int leftIndex, int rightIndex){
if(NULL == array){
printf("Invalid Input");
return;
}
if(leftIndex < rightIndex){
swap(array, leftIndex, rightIndex);
reverse(array, leftIndex+1, rightIndex-1);
}
}
Output
Enter number of elements in array: 6 Enter 6 numbers 1 2 3 4 5 6 Reversed Array 6 5 4 3 2 1
Related Topics
