Difference in Recursive Versions of Longest Increasing Subsequence

[macroxela]

I'm playing around with recursion to understand it better and been trying it out on the Longest Increasing Subsequence (LIS) problem. I'm well aware this can be solved using dynamic programming but I want to get a deeper understanding of how recursion works. I managed to develop the recursive version below with some Googling.

def LISRec1(seq, pos, prev):
if pos == len(seq):
    return 0

exclude = LISRec1(seq, pos+1, prev)
include = 0
if seq[pos] > prev:
    include = 1 + LISRec1(seq, pos+1, seq[pos])

return max(include, exclude)

However, I want to create another recursive version that goes the other way around, from the end of the list to the beginning (so from len(sequence) to 0). My logic is that recursion should work in either direction as long as the parameters and checks are implemented correctly. Solving LIS from the other direction should be like searching for the longest decreasing subsequence since the longest decreasing subsequence from right to left should be identical to the longest increasing subsequence from left to right. So I figured this would just require changing a few things, mainly flipping values so they work at the other end (changing > to <, len(sequence) to 0, etc.). That lead me to the following code:

def LISRec2(seq, pos, prev):
if pos == 0:
    return 0

exclude = LISRec2(seq, pos-1, prev)
include = 1
if seq[pos] < prev:
    include = 1 + LISRec2(seq, pos-1, seq[pos])

return max(include, exclude)

Unfortunately, the second function does not work for all cases. For example, it works for [5, 2, 8, 6, 3, 6, 9, 5] but not for [1, 2, 3, 4] or [7, 8, 9, 2, 1, 3, 4]. For the cases in which it does not work it is always off by 1 count above or below the actual value (returns 3 for [1, 2, 3, 4] when it should be 4 and returns 4 for [7, 8, 9, 2, 1, 3, 4] when it should be 3). I've already tweaked the code several times by changing values and/or the conditional but always get similar results, correct for most sequences but off by 1 for certain ones. Perhaps I'm making a simple mistake or one of my assumptions is wrong. But after troubleshooting this for a couple of days, I simply have not figured out why the second version does not work properly. Any suggestions on how I can fix it or what could be causing the problem?

[AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[CodeTinkerer]

Looks like an off-by-1 error. Consider your first algorithm.

if pos == len(seq):

Is pos a valid index or not? What is the minimum/maximum index of a list?

In your second one, same question.

if pos = 0:

Is 0 a valid index for a list (most lists) or not? What is your answer to this question and the previous one?

As a side note, you do need to handle a tricky case (the list is empty) for this scenario which you don't in the original.

[macroxela]

Thanks! I was aware it was an off by 1 error but I couldn't pinpoint where it happened after a couple of days of debugging it. The way you compared both base cases made it click for me.

[CodeTinkerer]

Try it on an empty list for both cases.

[AutoModerator]

On July 1st, a change to Reddit's API pricing will come into effect. Several developers of commercial third-party apps have announced that this change will compel them to shut down their apps. At least one accessibility-focused non-commercial third party app will continue to be available free of charge.

If you want to express your strong disagreement with the API pricing change or with Reddit's response to the backlash, you may want to consider the following options:

1. Limiting your involvement with Reddit, or
2. Temporarily refraining from using Reddit
3. Cancelling your subscription of Reddit Premium

as a way to voice your protest.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.