CODEWITHSUNDEEP
pythonrecursionlcs
priya
priya

Reputation: 129

Maximum Recursion in LCS Recursive Function

I'm trying to execute an LCS function that utilizes recursion to give me the number of positions the LCS is valid, along with the place of LCS depicted here:

input: LCS("smile", "tile")
output: [3, "##ile", "#ile"]

Whenever I try and execute it, it tells me that there is a recursion error, as follows:

RecursionError: maximum recursion depth exceeded in comparison

What is wrong with my code? I tried to replace the areas where LCS didn't apply through recursion, but where does the function exceed its depth?

def LCS(s1, s2):
    if s1 == "" or s2 == "":
        return 0
    else:
        if s1[0] == s2[0]:
            s1 = s1 + s1[0]
            s2 = s2 + s2[0]
            count = 1 + LCS(s1[1:], s2[1:])
        else: 
            s1 = s1 + '#'
            count = max(LCS(s1, s2[1:]), LCS(s1[1:], s2))
    array = [count] + [s1] + [s2]
    print(array)

Upvotes: 3

Views: 389

Answers (3)

trincot
trincot

Reputation: 349954

As stated by others you are adding a character to your string variable, and chop one off in the next recursive call. This way there will always be recursive calls with a string that has the initial length, leading to infinite recursion.

And with a closer look, this does not make sense:

    if s1[0] == s2[0]:
        s1 = s1 + s1[0]

Here you add the first character to the end of the string again. This cannot be right.

Also, the function has the ability to return only 0 (or None), but nothing else. This also cannot be right. Whatever the function does, it should always return a value.

As you are interested in the count of matching characters and the # filled versions of both original strings, you could let your function return three values (a list) instead of one.

The code could then be made to work like this:

def LCS(s1, s2):
    if s1 == "" or s2 == "":
        return 0, '#' * len(s1), '#' * len(s2)
    else:
        if s1[0] == s2[0]:
            count, r1, r2 = LCS(s1[1:], s2[1:])
            return  count+1, s1[0] + r1, s2[0] + r2
        else:
            count1, r11, r12 = LCS(s1, s2[1:])
            count2, r21, r22 = LCS(s1[1:], s2)
            if count2 > count1:
                return count2, '#' + r21, r22
            else:
                return count1, r11, '#' + r12

print (LCS ('smile', 'tile'))

Output:

(3, '##ile', '#ile')

Upvotes: 1

Prune
Prune

Reputation: 77827

I'm not at all clear about your logic: on each iteration, you either move the first character to the end of the string, or you drop it and append a #. The only reduction step in this is shortening s2 in the lower branch, but you'll get caught in infinite recursion before you get there. I added a simple tracing print to the top of the routine:

def LCS(s1, s2):
    print("ENTER s1=", s1, "\ts2=", s2)

Here's how it gets stuck:

ENTER s1= smile     s2= tile
ENTER s1= smile#    s2= ile
ENTER s1= smile##   s2= le
ENTER s1= smile###  s2= e
ENTER s1= smile####     s2= 
ENTER s1= mile####  s2= e
ENTER s1= mile#####     s2= 
ENTER s1= ile#####  s2= e
ENTER s1= ile######     s2= 
ENTER s1= le######  s2= e
ENTER s1= le#######     s2= 
ENTER s1= e#######  s2= e
ENTER s1= #######e  s2= e
ENTER s1= #######e#     s2= 
ENTER s1= ######e#  s2= e
ENTER s1= ######e##     s2= 
ENTER s1= #####e##  s2= e
ENTER s1= #####e###     s2= 
ENTER s1= ####e###  s2= e
ENTER s1= ####e####     s2= 
ENTER s1= ###e####  s2= e
ENTER s1= ###e#####     s2= 
ENTER s1= ##e#####  s2= e
ENTER s1= ##e######     s2= 
ENTER s1= #e######  s2= e
ENTER s1= #e#######     s2= 
ENTER s1= e#######  s2= e
ENTER s1= #######e  s2= e

When you fail in a run, you need to reset s2 to its original value. Your present code backs up with one more character on each string, leaving s2 permanently bouncing between its last character and NULL.

Upvotes: 0

Scott Hunter
Scott Hunter

Reputation: 49803

In your first recursive call (count = 1 + LCS(s1[1:], s2[1:])), since you just added an element to the end of each of s1 and s2, the sizes of strings being passed are the same as in the call, so you are making no progress towards termination

Inside of max, the second recursive call has the same problem: you added an element to s1, so the sizes of the string being passed are the same as in the call.

Upvotes: 1

Related Questions