Iterative and recursive implementations of LCS-Length() in Python

lcslen.py

#!/usr/bin/env python3

def LCS_length(X, Y):
    m = len(X)
    n = len(Y)

    c = [[0 for j in range(n+1)] for i in range(m+1)]

    for i in range(0, m):
        for j in range(0, n):
            if X[i] == Y[j]:
                c[i][j] = c[i-1][j-1] + 1
            elif c[i-1][j] >= c[i][j-1]:
                c[i][j] = c[i-1][j]
            else:
                c[i][j] = c[i][j-1]

    return c[m-1][n-1]

def LCS_length_rec(X, Y, i=None, j=None):
    if i is None and j is None:
        return LCS_length_rec(X, Y, i=len(X)-1, j=len(Y)-1)

    if i == -1 or j == -1:
        return 0
    if X[i] == Y[j]:
        return LCS_length_rec(X, Y, i=i-1, j=j-1) + 1
    else:
        return max(LCS_length_rec(X, Y, i=i, j=j-1), LCS_length_rec(X, Y, i=i-1, j=j))

lcslen_test.py

#!/usr/bin/env python3
import unittest

import lcslen

class LCSTests(unittest.TestCase):
    def test_lcs_length(self):
        seq = [ # (X, Y, lCSLength)
            ("ABCBDAB", "BDCABA", 4),
            ("XTREQ", "TLLRDDDSAE", 3),
            ("TEST", "TEST", 4)
        ]

        for test in seq:
            iter_result = lcslen.LCS_length(test[0], test[1])
            rec_result = lcslen.LCS_length_rec(test[0], test[1])

            # Check that both versions of LCS-Length return the same result
            # for the same input.
            self.assertEqual(iter_result, rec_result)

            # Check that the result matches the expected result.
            self.assertEqual(rec_result, test[2])


if __name__ == '__main__':
    unittest.main()