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

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

python recursion lcs