10.1.1. What is Recursion?
Recursion is when a method calls itself. See the example method below.
public static void neverEnd()
1
{
2
System.out.println("This is the method that never ends!");
3
neverEnd();
4
}
5
This method will print out “This is the method that never ends!” and then call itself,
which will print out the message again, and then call itself, and so on. This is
called infinite recursion, which is a recursion that never ends. Of course, this particular
method is not very useful.
10.1.2. Why use Recursion?
Recursion is most useful when it is used to solve problems where the structure of the
problem repeats. For example, what if you wanted to find out how much space a folder
on your computers uses? You could add up the sizes of all the files in that folder, but
folders can also contain subfolders. So you will have to repeat the procedure (method)
for each subfolder. Each subfolder can also contain subfolders.
Recursion can also be used to create fractals. A simple example is Sierpinski’s triangle in
which you subdivide a triangle into 4 new triangles as shown below. You can then do
the some procedure with each new triangle except the center one.
A sequence of Sierpinski’s triangles
Recursion can also be used to traverse String, array, and ArrayList objects, much like a
loop. In fact, any recursive solution could be written with iteration (loops) instead.
10.1.3. Factorial Method
1 public static int factorial(int n)
2 {
3 if (n == 0)
4 return 1;
5 else
6 return n * factorial(n-1);
7 }
public class FactorialTest
{
public static int factorial(int n)
{
if (n == 0)
return 1;
else
return n * factorial(n-1);
}
public static void main(String[] args)
{
System.out.println("factorial of 3 is: " + factorial(3));
System.out.println("factorial of 4 is: " +factorial(4));
System.out.println("factorial of 5 is: " +factorial(5));
}
}
Tracing Recursive Methods
public static int mystery(int n)
{
if (n == 0)
return 1;
else
return 3 * mystery (n - 1);
}
Recursive Binary Search
public class IterativeBinarySearch
{
public static int binarySearch(int[] elements, int target) {
int left = 0;
int right = elements.length - 1;
while (left <= right)
{
int middle = (left + right) / 2;
if (target < elements[middle])
{
right = middle - 1;
}
else if (target > elements[middle])
{
left = middle + 1;
}
else {
return middle;
}
}
return -1;
}
public static void main(String[] args)
{
int[] arr1 = {-20, 3, 15, 81, 432};
int index = binarySearch(arr1,81);
System.out.println(index);
}
}
Merge Sort
import java.util.Arrays;
public class SortTest
{
public static void mergeSort(int[] elements)
{
int n = elements.length;
int[] temp = new int[n];
mergeSortHelper(elements, 0, n - 1, temp);
}
private static void mergeSortHelper(int[] elements, int from, int to, int[] temp)
{
if (from < to)
{
int middle = (from + to) / 2;
mergeSortHelper(elements, from, middle, temp);
mergeSortHelper(elements, middle + 1, to, temp);
merge(elements, from, middle, to, temp);
}
}
private static void merge(int[] elements, int from, int mid, int to, int[] temp)
{
int i = from;
int j = mid + 1;
int k = from;
while (i <= mid && j <= to)
{
if (elements[i] < elements[j])
{
temp[k] = elements[i];
i++;
}
else
{
temp[k] = elements[j];
j++;
}
k++;
}
while (i <= mid)
{
temp[k] = elements[i];
i++;
k++;
}
while (j <= to)
{
temp[k] = elements[j];
j++;
k++;
}
for (k = from; k <= to; k++)
{
elements[k] = temp[k];
}
}
public static void main(String[] args)
{
int[] arr1 = {86, 3, 43, 5};
System.out.println(Arrays.toString(arr1));
mergeSort(arr1);
System.out.println(Arrays.toString(arr1));
}
}
