# Recursive Algorithms

## Recursion

• Base case
``````void countDown() {

}``````

## Examples

#### Greatest common divisor (gcd)

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

#### Fibonacci numbers

0, 1, 1, 2, 3, 5, 8, 13, ... fib(n)

• fib(n) = fib(n-1) + fib(n-2)

• Base case: n==0 , n == 1

```// 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);

}
```

#### Summing a list of numbers

```// 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) {

}
```

#### Computing Power of a number \$x^y\$

``````
``````