There are two problems with a recursive solution:
1. Recursion requires more memory and time, particularly if the array is passed by value (all elements are copied on each call) rather than reference (a pointer). Each function call creates more variables on the call stack. For a very large array of integers, this overhead would become excessive. Unless you know you have a relatively small array and time and memory are not an issue, it is better to use an iterative approach or to replace recursive function calls with your own stack which you may design to minimize memory usage.
2. For a sequence of numbers, if you find the largest subsequence in a subarray, you'll need to test whether it occurs on the boundaries or inside (i.e., it does not include the first or last elements). If it does start or end the subarray, then as you process the return from the innermost recursive calls, you'll need to test for boundary conditions to see if the subsequence continues adjacent to the subarray you analyzed in the function. This requires far more complex logic than a simple iterative solution.
With that in mind, I would recommend the following:
1. Divide your array as you would in a binary search. For the first call, pass the first half of the array in one function call, the second in another.
2. Inside the recursive function, further subdivide into first half and second half.
3. Choose a limit on the size, e.g. 20 elements. If the call to the recursive function is for a subarray with < 20 elements, solve that subarray iteratively.
4. Pass back the following information:
a. Size of longest monotonically increasing subsequence.
b. Location (starting index) of longest subsequence.
c. Boundary status (0 = internal, 1 = start of subarray, 2 = end of subarray, 3 = full subarray)
5. In the calling function, compare the results of the two halves. Unless the boundary is end for the first or start for the second, choose the larger of the two and return that. Be sure to compute the new boundary status for the full array in this recursive call.
6. Else, if the longest for the first half borders on the end and the longest for the second half borders on the beginning, then your solution is the combination of the two (length1 + length2, starting at the index of the first half). Be sure to compute the new boundary status for the full array in this recursive call.
7. Else, make another recursive call for the subarray which spans the midpoint of the original two subarrays. This will depend upon the boundary statuses:
a. First array (left) has solution which borders on midpoint (2 or 3) and second array (right) has solution which does not (0 or 2): New array starts at index of first solution and adds (length2 - 1) in size.
b. Second array (right) has solution which borders on midpoint (1 or 3) and first array (left) has solution which does not (0 or 1): Start new array (length1 - 1) before the midpoint and add (length1 - 1) to length2.
8. If the new array (lenght3) is more than length1 or lenght2, return that. Otherwise, return the greater of length1 and length2, with the respective starting index. Be sure to compute the new boundary status for the full array in this recursive call.