Non-tail recursion within a for loop

Question

Given an array of numbers, find the length of the longest increasing subsequence in the array. The subsequence does not necessarily have to be contiguous.

For example, given the array [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], the longest increasing subsequence has length 6: it is 0, 2, 6, 9, 11, 15.

One of the solutions to the above problem uses non-tail recursion within a for loop, and I am having trouble making sense of it. I don't understand when the code after the recursive call in the for loop is executed, and I can't visualize the entire execution process of the whole solution.

def longest_increasing_subsequence(arr):
    if not arr:
        return 0
    if len(arr) == 1:
        return 1

    max_ending_here = 0
    for i in range(len(arr)):
        ending_at_i = longest_increasing_subsequence(arr[:i])
        if arr[-1] > arr[i - 1] and ending_at_i + 1 > max_ending_here:
            max_ending_here = ending_at_i + 1
    return max_ending_here

The description of the solution is as follows:

Assume that we already have a function that gives us the length of the longest increasing subsequence. Then we’ll try to feed some part of our input array back to it and try to extend the result. Our base cases are: the empty list, returning 0, and an array with one element, returning 1.

Then,

• For every index i up until the second to last element, calculate longest_increasing_subsequence up to there.
• We can only extend the result with the last element if our last element is greater than arr[i] (since otherwise, it’s not increasing).
• Keep track of the largest result.

Source: https://www.dailycodingproblem.com/blog/longest-increasing-subsequence/

---

**EDITS**:

What I mean by I don't understand when the code after the recursive call in the for loop is executed. Here is my understanding:

0. Some code calls lis([0, 8, 4, 12, 2]).
1. arr = [0, 8, 4, 12, 2] doesn't meet either of the two base cases.
2. The for loop makes the first call when i = 0 in the line ending_at_i = lis([]). This is the first base case, so it returns 0. I can't understand why control doesn't return to the for loop so that ending_at_i is set to 0, and the if condition is executed (because it surely isn't checked else [][-1] would throw an error), after which we can move on to the for loop making the second call when i = 1, third call when i = 2 which would branch into two calls, and so on.

Answer 1

Here's how this function works. Fist, it handles the degenerate cases where the list length is 0 or 1.

It then looks for the solution when the list length is >= 2. There are two possibilities for the longest sequence: (1) It may contain the last number in the list, or (2) It may not contain the last number in the list.

For case (1), if the last number in the list is in the longest sequence, then the number before it in the longest sequence must be one of the earlier numbers. Suppose the number before it in the sequence is at position x. Then the longest sequence is the longest sequence taken from the numbers in the list up to and including x, plus the last number in the list. So it recurses on all of the possible positions of x, which are 0 through the list length minus 2. It iterates i over range(len(arr)), which is 0 through len(arr)-1). But it then uses i as the upper bound in the slice, so the last element in the slice corresponds to indices -1 through len(arr)-2. In the case of -1, this is an empty slice, which handles the case where all values in the list before the last are >= the last element.

This handles case (1). For case (2), we just need to find the largest sequence from the sublist that excludes the last element. However, this check is missing from the posted code, which is why the wrong answer is given for a list like [1, 2, 3, 0]:

>>> longest_increasing_subsequence([1, 2, 3, 0])
0
>>> 

Obviously the correct answer in this case is 3, not 0. This is fairly easy to fix, but somehow was left out of the posted version.

Also, as others have pointed out, creating a new slice each time it recurses is unnecessary and inefficient. All that's needed is to pass the length of the sublist to achieve the same result.

Answer 2

Here is a (hopefully good enough) explanation:

ending_at_i = the length of the LIS when you clip arr at the i-th index (that is, considering elements arr[0], arr[1], ..., arr[i-1].

if arr[-1] > arr[i - 1] and ending_at_i + 1 > max_ending_here

if arr[-1] > arr[i - 1] = if the last element of arr is greater than the last element of the part of arr correponding to ending_at_i

if ending_at_i + 1 > max_ending_here = if appending the last element of arr to the LIS found during computing ending_at_i is larger than the current best LIS

The recursive step is then:

1. Let an oracle tell you the length of the LIS in arr[:i] (= arr[0], arr[1], ..., arr[i-1])

   • realize that, if the last element of arr, that is, arr[-1], is larger than the last element of arr[:i], then whatever the LIS inside arr[:i] was, if you take it and append arr[-1], it will still be an LIS, except that it will be one element larger

2. Check whether arr[-1] is actually larger than arr[i-1], (= arr[:i][-1])

3. Check whether appending arr[-1] to the LIS of arr[:i] creates the new optimal solution

4. Repeat 1., 2., 3. for i in range(len(arr)).

5. The result will be the knowledge of the length of the LIS inside arr.

All that being said, since the recursive substep of this algorithm runs in O(n), there are very few worse feasible solutions to the problem.

You tagged dynamic programming, however, this is precisely the anti-example of such. Dynamic programming lets you reuse the solutions to subproblems, which is precisely what this algorithm doesn't do, hence wasting time. Check out a DP solution instead.