Recursive Algorithms

int gcd(int x, int y) {
    if (x % y == 0) // base case
        return y;
    else
        return gcd(y, x % y);
}

// algorithm 1: very inefficient
int fib(int n)  
{
   if (n==0) // base case
       return 0;
   else if (n==1) //base case
       return 1;
   else
       return fib(n-1) + fib(n-2);
}

int bSearch(int a[], int lo, int hi, int x) {
    int m = (lo + hi) / 2;
    if (lo > hi) return -1;  // base case 1
    if (a[m] == x) return m;
    if (a[m] > x)
        return bSearch(a, lo, m-1, x);
    else
        return bSearch(a, m+1, hi, x);

}

// Algorithm 1: O(N) 
int arraySum(int arr[], int size) {
    if (size == 0)
        return 0;
    else
        return arraySum(arr, size-1) + arr[size - 1];
}

// Algorithm 2: O(log N)
int arraySum(int arr[], int size) {

}