In mathematics, the greatest common divisor (GCD) of two or more integers, when at least one of them is not zero, is the largest positive integer that is a divisor of both numbers. For example, the GCD of 8 and 12 is 4. You have to write a function to find Greatest Common Divisor (GCD) of 2 numbers using recursion.

Your function signature should look like this:

int gcd(int n1, int n2);

Following main() should work with your code:

In sequential search (whatever we have done so far, especially in hw3, where we implemented templated find() for STLs), when we compare against the first item, there are at most n1 more items to look through if the first item is not what we are looking for.

Now, let us assume that we are given a sorted array. It is possible to avoid traversing the entire array by spot-checking elements in the middle. For example, if we are looking for 7 in an array like [0, 3, 4, 5, 7, 9, 11, 15, 17, 21, 23, 34]; we can pick an element from the middle - say 15 (we could choose either 11 or 15) to find if 15 is greater than 7 and then skip searching right side of the array [17, 21, 23, 34]. Instead we can repeat our search on the left side [0, 3, 4, 5, 7, 9, 11]. Thus avoiding traversing through all elements. This is called binary search.

A basic pseudocode is given below:

You have to write a recursive function with the given signature,

int binarySearch(int arr[], int left, int right, int elem_to_find);

Such that, it should return -1 if the element is not found, otherwise return the index at which the element is found.

The main() given below:

int main() { cout etc should be here int binarySearch(int arr[], int left, int right, int elem_to_find) { // Your code goes here } // do NOT change this int binarySearch(int arr[], int len, int elem_to_find) { return binarySearch(arr, 0, len - 1, elem_to_find); } int main() { int arr[] = {2, 3, 4, 10, 40}; int n = sizeof(arr)/ sizeof(arr[0]); int x = 10; int result = binarySearch(arr, n, x); if (result == -1) { cout