Hey there! Let's break down why your recursive LCS code is throwing that index error and get it working properly.

The Root Cause #

The main issue is your base case check—it doesn't handle empty strings, which is the natural stopping point for this recursive approach. Let's look at the problematic line:

if any((s1, s2)) is None:
    return 0

The any() function returns a boolean (True or False), so comparing that result to None will always be False. That means your base case never triggers, even after slicing strings down to nothing. When you try to access s1[-1] or s2[-1] on an empty string, you get the "string index out of range" error.

On top of that, there's a small mistake in your final recursive call: you swapped s1 and s2 incorrectly, which would lead to unexpected behavior even if the index error was fixed.

The Corrected Code #

Here's the fixed version with proper base cases and corrected recursion:

def lcs(s1, s2):
    # Handle None inputs first
    if s1 is None or s2 is None:
        return 0
    # Stop recursion when either string is empty
    if len(s1) == 0 or len(s2) == 0:
        return 0
    # If last characters match, count it and recurse on the rest
    if s1[-1] == s2[-1]:
        return 1 + lcs(s1[:-1], s2[:-1])
    # Otherwise, recurse by removing last character from each string and take max
    return max(lcs(s1, s2[:-1]), lcs(s1[:-1], s2))

print(lcs("ABDER", "ADFRTY"))  # Output: 3 (matches "A", "D", "R")

Key Fixes Explained: #

• Proper Base Cases: We first check for None inputs, then stop recursion when either string is empty. This prevents invalid character access on empty strings.
• Simplified Slicing: s1[:-1] is a cleaner way to get all characters except the last one, replacing the verbose s1[:len(s1)-1].
• Fixed Recursive Call: The second call in max() was swapped incorrectly—now it correctly passes s1[:-1] and s2 instead of swapping the parameters, keeping the logic consistent.

This code will now correctly compute the length of the longest common subsequence for your test inputs, and avoid the index error entirely.

内容的提问来源于stack exchange，提问作者Tilak Madichetti