Maximum Recursion in LCS Recursive Function
<p>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:</p>

<pre><code>input: LCS("smile", "tile")
output: [3, "##ile", "#ile"]
</code></pre>

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

<pre><code>RecursionError: maximum recursion depth exceeded in comparison
</code></pre>

<p>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?</p>

<pre><code>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)
</code></pre>

<p>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 <strong>#</strong>.
The <em>only</em> 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:</p>

<pre><code>def LCS(s1, s2):
    print("ENTER s1=", s1, "\ts2=", s2)
</code></pre>

<p>Here's how it gets stuck:</p>

<pre><code>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
</code></pre>

<hr>

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

python recursion lcs