Reversing an array using Recursion is an example of Tail Recursion . We maintain two in-variants “i” and “j”. “i” holds starting element index and “j” holds ending element index of the array. As long as “i” is less than “j”, we swap two elements starting and ending element of the array. Increment “i” and decrement “j” and solve the similar problem for the rest of the array until two in-variants “i” and “j” cross over.
Algorithm or Recurrence relation for Reversing an Array
if (i<j) then
swap elements a[i],a[j] //i holds starting index,
//j holds ending index of array.
reverse(a,i+1,j-1)Reversing an array using Recursion – Implementation in Java
Here is the impementation for Reversing an array using recursion in java
ReversingArrayUsingRecursion.java
x
45
1
package com.jminded.recursion;2
3
public class ReversingArrayUsingRecursion {4
5
/**6
* @author Umashankar7
* {@link https://jminded.com}8
* @param args9
*/10
public static void main(String[] args) {11
// TODO Auto-generated method stub12
//input : arr={0,1,2,3,4,5,6,7,8}13
//output : arr={8,7,6,5,4,3,2,1,0}14
int[] arr={0,1,2,3,4,5,6,7,8};15
int length=arr.length;16
int[] revArray=reverseArray(arr,0,length-1);17
//loop through array for display.18
for(int i:revArray)19
System.out.print(i+" ");20
21
}22
/**23
* <p>Reversing array using Recursion24
* Example of Tail Recursion.25
* </p>26
* if (i<j) then 27
* swap elements a[i],a[j] //i holds starting index, j holds ending index of array.28
* reverse(a,i+1,j-1)29
* @param a30
* @param i31
* @param j32
* @return33
*/34
public static int[] reverseArray(int[] a,int i,int j){35
//Tail Recursion.36
if(i<j){37
//swap elements a[i],a[j]38
int temp=a[i];39
a[i]=a[j];40
a[j]=temp;41
reverseArray(a, i+1, j-1);42
}43
return a;44
}45
}Output
8 7 6 5 4 3 2 1 0