Recursion
We suppose that you have seen iterative methods in the prerequisite courses. Methods using a loop such as for loops, while loops,
or do-while loops are considered to be iterative. Often we can compute the same result using recursion (without using a loop.)
In some cases, using recursion enables you to give a natural, straight forward, simple solution to a program that would otherwise be
difficult to solve.
What is a recursive method?
-A method that invokes itself (direct recursion)
Example:
public void methodA()
{
methodA();
}
Of course the methodA keeps calling itself and this will generate an infinite recursion. Thus we need a stopping condition
where it does not call itself.
Recursion should have:
- recursive case(s)
- base case(s) (non-recursive part, stopping condition)
If there is no base case, there will be no way to terminate the recursive path. → infinite recursion
Example:
For a given positive integer n (i.e., n = 1, 2, 3, 4, …), the method sum is defined by: sum(n) = 1+2+ … + n
Using a loop (iterative), this can be computed using a variable that shows the accumulated value for the sum.
(here the variable is “result”)
public static int sum(int n)
{
int result = 1;
for (int i=2; i<=n; i++)
result = result + i; //in this line, “result” on the right hand side is the old value of result, containing the sum from 1 to (i-1)
//and the “result on the left hand side if the new value containing the sum from 1 to i.
return result;
}
By observing the pattern from the previous slide, we can formulate the recursion:
Base case: sum(1) = 1 for n=1
Iterative case: sum(k) = sum(k-1) + k for k >= 2
(This means that, assuming that we have already computed the sum up to k-1, we can compute the sum up to k.)
The second line is recursive since you see the same function in both sides of the equation.
Based on the above observation, we have the following recursive method to compute the sums.
Recursive method
// assume that n >= 1
public static int sum(int n)
{
int result;
if (n == 1) // base case
result = 1;
else //recursive case for n >= 2
result = sum(n-1) + n;
return result;
}
main
sum
sum
sum
sum
sum(4)
is invoked
sum(3)
is invoked
sum(2)
is invoked
sum(1)
is invoked
sum(1)=1 is returned
sum(2)= sum(1) + 2=2+1is returned
sum(3)= sum(2) + 3=3+3is returned
sum(4)= sum(3) + 4=4+6is returned
public static void main(String[] args)
{
int result = sum(4);
}
This method can be called from a main method as:
Observe that the sum using a recursive method can be computed in two passes.
going down to the base case, then going up!
1
+2
+3
+4
Iterative method
public static int sum(int n)
{
int result = 1;
for (int i=2; i<=n; i++)
result = result + i;
return result;
}
Recursive method
// assume that i >= 1
public static int sum(int i)
{
int result;
if (i == 1) // base case
result = 1;
else //recursive case for i >= 2
result = sum(i-1) + i;
return result;
}
Now you can see these two methods side by side. They compute the exactly same result, but one is iterative and
the other is recursive.
How to construct a recursive method:
1. Identify your sub-problem. i.e., the same problem as the original problem, but on a subset of the original input.
2. Think how you can use a solution of the sub-problem to solve the original problem.
With the above example, the original problem is to compute the sum from 1 to n, and the sub-problem is to compute the sum from 1 to n-1.
If we had the sum from 1 to (n-1), then we just need to add n to it to get the sum from 1 to n.
3. Also consider your base case(s).
4. When converting an iterative method to a recursive method, in some cases additional parameter(s) might be needed.
One such parameter is the variable used to increment or decrement the loop in iterative methods.
public static void mergeSort(int[] num, int start, int end)
{
//base case is when start == end, does nothing
if (start < end) //recursive case
{
int mid = (int) Math.floor((double) (start+end)/(2.0));
mergeSort(num,start,mid);
mergeSort(num,mid+1,end);
merge(num, start, mid, end);
}
}
The method “mergeSort” splits an array into two
subarrays and invokes itself on them.
(“start” is the starting index and “end” is the ending index.)
The method “merge” merges two subarrays into one
array without disturbing their order.
The complexity of Merge Sort Algorithm is order of
n log n. Therefore Merge Sort is more efficient than
Selection Sort and Insertion Sort in their worst case.
The mergeSort method invokes merge method described in the next page.
The merge method merges two sorted subarrays into one.
2 5 6 9 13 14
1 3 4 7 10 12
1 2 3 4 5 6 7 9 10 12 13 14
public static void merge(int[] num, int start, int mid, int end)
{
int n1 = mid-start+1; //get the length of the first half subarray
int n2 = end-mid; //get the length of the second half subarray
int[] left = new int[n1];
int[] right = new int[n2];
//i is used for the array "left", j for "right", k for "num"
int i, j, k;
// copy the elements in the array "num" to the arrays
// "left" and "right"
for (i=0; i<n1; i++)
left[i] = num[start+i];
for (j=0; j<n2; j++)
right[j] = num[mid+1+j];
i=0;
j=0;
k=start;
while (i < n1 && j < n2) //merge left and right into "num"
{
if (left[i] <= right[j])
{
num[k] = left[i];
i++;
}
else
{
num[k] = right[j];
j++;
}
k++;
}
// copy the rest of the subarray that did not get copied
if ( i == n1)
{
while (k <= end)
{
num[k] = right[j];
k++;
j++;
}
}
else if (j == n2)
{
while (k <= end)
{
num[k] = left[i];
k++;
i++;
}
}
}
Binary Search using Recursion:
public static int binSearch(int[] num, int x)
{
int n = num.length;
if (n == 0 || x > num[n-1] || x < num[0])
return -1; // x is not found
else
return binRec(num,x,0,n-1);
}
public static int binRec(int[] num, int x, int i, int j)
{
//base cases
if (i==j && num[i]==x)
return i; // x is found
else if (i==j && num[i]!=x)
return -1; // x is not found
int k = (int) Math.floor((i+j)/(2.0));
//recursive cases
if (x<=num[k])
return binRec(num, x, i, k);
else
return binRec(num, x, k+1, j);
}
Powered by TCPDF (www.tcpdf.org)
