Finding large & small element by Recursion without using Loops

This code was one of the assignments given to me in college. I had to break my head to work this out, and then finally found out that the program code was already present in my text book. But anyway, its always better to develop our own codes than referring to textbooks. So in this post i am sharing the code with the output as well as explanation with the help of a table.

[java]

class rsort
{
public static void main(String args[])
{
int a[]={5,3,2,1,4}; // or choose int a[] = {3,2,8,1,4};
int n = a.length;

for(int i=0; i<n; i++)
{
System.out.print(" " + a[i]);
}
System.out.println("");

System.out.println("Max = " + max(a, 0, n-1));
System.out.println("Min = " + min(a, 0, n-1));
}

static int max(int a[], int start, int end)
{
if(start<end)
{
if(a[start]<a[end])
{
return max(a, start+1, end);
}

return max(a, start, end-1);
}
return a[end];
}

static int min(int a[], int start, int end)
{
if(start<end)
{
if(a[start]>a[end])
{
return min(a, start+1, end);
}

return min(a, start, end-1);
}
return a[end];
}
}

[/java]

Output

Explanation of Max Recursive Method

  • As you can see in the image below, the depth of recursion is five.
  • Five recursive methods have been called to get the large (max) number.
  1. At the beginning the array {5,3,2,1,4} is passed into the rsort function with parameters (a, 0, n-1)
  2. where a is the array, 0 is the first index of array and n-1 is the last index of array.
  3. The rsort function accepts these values as follows : a is taken as a, 0 is taken as start, n-1 is taken as end.
  4. (a, 0, n-1) = (a, start, end) = (a, 0, 4)
  5. (start < end ? ) = (0 < 4 ? ) = Yes.
  6. (a[start] < a[end] ? ) = (5<4 ? ) = No.
  7. Recursive call (a, start, end-1) = (a, 0, 4-1) = (a,0, 3)
  8. (start < end ? ) = (0<3 ? ) = Yes.
  9. (a[start] < a[end] ? ) = (5<1 ? ) = No.
  10. Recursive call (a, start, end-1) = (a, 0, 3-1) = (a,0,2)
  11. And so on.. Check the table below for relevance and better understanding.

Leave a Reply