Question

Algorithm to calculate and return the length of a list

Answer 1

Recursive algorithms gain efficiency by reducing the scope of the problem until the solution is trivial. Thus, we need to define the problem in terms of sub-array. With that in mind, we can define longest-increasing subsection as the first array element plus the longest-increasing subsection of all remaining elements that are greater than that first array element.

In pseudo-code: LIS(a) = a[0] + LIS(a[1:]>a[0])

Now that we have that definition, we need a terminal state. Since the last subarray in this definition will be an empty array, that is the terminal state. if(a == []): return 0 will be the end of the recursive chain.