• • write a recursive function to find longest increasing subsequence using recursion. For example if we have sequence of  { 6, 3, 4, 5, 6, 9, 8 }. The longest increasing subsequence is {3,4,5,6,9} or {3,4,5,6,8} and its length is 5. Your recursive program should print 5 in this test case.

### sample program longest increasing subsequence using recursion

```#include <iostream>
#include<algorithm>
#include<climits>
using namespace std;

int mx = 0;

void lis(int index, int *arr, int arr_len, int prev, int c) {

if (index >= arr_len) {
if (c >= mx)
mx = c;

c = 0;
return;
}

lis(index + 1, arr, arr_len, prev, c);

if (arr[index] > prev) {
lis(index + 1, arr, arr_len, arr[index], c + 1);
}
}

int main() {
int arr[] = { 6, 3, 4, 5, 6, 9, 8 };
lis(0, arr, sizeof(arr) / sizeof(int), INT_MIN, 0);
cout << mx << endl;
return 0;
}
```

## Big O complexity

The time complexity of above program would be O(2^n) where n is length of inputs.  it is exponential, since each function call calls itself twice. The above solution is not efficient and can be solved with O(n^2) complexity through dynamic programming (http://wikistack.com/longest-increasing-subsequence-dynamic-programming/).