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

<p>And with a closer look, this does not make sense:</p>

<pre><code>    if s1[0] == s2[0]:
        s1 = s1 + s1[0]
</code></pre>

<p>Here you add the <em>first</em> character to the <em>end</em> of the string again. This cannot be right.</p>

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

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

<p>The code could then be made to work like this:</p>

<pre><code>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 &gt; count1:
                return count2, '#' + r21, r22
            else:
                return count1, r11, '#' + r12

print (LCS ('smile', 'tile'))
</code></pre>

<p>Output:</p>

<pre><code>(3, '##ile', '#ile')
</code></pre>

<p>See it run on <a href="https://repl.it/Dbix/2" rel="nofollow">repl.it</a>.</p>

python recursion lcs