Reversing an array using Recursion in Java

by

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

package com.jminded.recursion;

public class ReversingArrayUsingRecursion {

	/**
	 * @author Umashankar
	 * {@link https://jminded.com}
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//input    : arr={0,1,2,3,4,5,6,7,8}
		//output   : arr={8,7,6,5,4,3,2,1,0}
		int[] arr={0,1,2,3,4,5,6,7,8};
		int length=arr.length;
		int[] revArray=reverseArray(arr,0,length-1);
		//loop through array for display.
		for(int i:revArray)
			System.out.print(i+" ");

	}
	/**
	 * <p>Reversing array using Recursion
	 *   Example of Tail Recursion.
	 * </p>
	 *   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)
	 * @param a
	 * @param i
	 * @param j
	 * @return
	 */
	public static int[] reverseArray(int[] a,int i,int j){
		//Tail Recursion.
		if(i<j){
			//swap elements a[i],a[j]
			int temp=a[i];
			a[i]=a[j];
			a[j]=temp;
			reverseArray(a, i+1, j-1);
		}
		return a;
	}
}

 Output

8 7 6 5 4 3 2 1 0

Leave a Comment