9/2 Recursion

Let us consider what happens when we make the following changes to the
function fibo that we wrote on Wednesday.

public static int fibo(int n)
{
	if (n == 1)
		return 1;
	else 
		return fibo(n-1) + fibo(n-2);
}

This will cause an infinite loop when fibo(2) is called. The sequence 
of calls will be

fibo(2), fibo(1), fibo(0), fibo(-1), fibo(-2), fibo(-3),....

This happens because the base case is not complete. The base case needs
to provide correct answers to a small set of problems such that any
larger problem can be reduced, via recursion, to one or more of the base
case problems.

Example: Recursive binary search

The following function is just the "wrapper" for the recursive
function. It is not reasonable to assume that the user will always
send in all the relevant parameters needed to make the recursion
go through. So it might be necessary to write a wrapper function
that calls the recursive version of the function with appropriate
parameters.


public static boolean binarySearch(int[] data, int key, int n)
{
	recursiveBinarySearch(data, key, 0, n-1);
}

public static boolean recursiveBinarySearch(int[] data, int key, int first, int last)
{
	// base case 1
	if (first > last)
		return false;
	
	int mid = (first + last)/2;
	// base case 2
	if (key == data[mid])
		return true;

	// recursive case 1
	else if(key < data[mid])
		return recursiveBinarySearch(data, key, first, mid-1);

	// recursive case 2
	else if(key > data[mid])
		return recursiveBinarySearch(data, key, mid+1, last);
}


Suppose the array data contains 10 elements

	index		0  1  2  3  4  5  6  7  8  9
	element 	3  3  6  9  11 12 15 16 19 22

Suppose we are looking for key = 5. Then the sequence of calls that will be
made are:

	(0, 9) -> (0, 3) -> (2, 3) -> (2, 1)

The above algorithm for binary search is an example of the "divide-and-conquer"
technique. By using the value of mid, the problem is divided into three smaller
problems:

	(1) Look in data[mid] for key.

	(2) Look in data[first..mid-1] for key.

	(3) Look in data[mid+1..last] for key.

Problem (1) can be solved in one step and there is no need for recursion there.
Problems (2) and (3) are just smaller instances of the same search problem. Note 
that what makes binary search so efficient is that only one of the two problems
needs to be solved.