Data Structures and Algorithms - Old Questions
4. What is Recursion? Write a recursive algorithm to implement binary search.
5 marks
|
Asked in 2072
Recursion is a process by which a function calls itself repeatedly, until some specified condition has been satisfied. The process is used for repetitive computations in which each action is stated in terms of a previous result.
Recursive algorithm to implement binary search
int binarySearch(int A[], int low, int high, int x)
{
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (x == A[mid]) {
return mid;
}
else if (x < A[mid]) {
return binarySearch(A, low, mid - 1, x);
}
else {
return binarySearch(A, mid + 1, high, x);
}
}