Question: I am trying to return the length of a common substring between two strings. I'm very well aware of the DP solution, however I want to be able to solve this recursively just for practice.

I have the solution to find the longest common subsequence...

```
def get_substring(str1, str2, i, j):
    if i == 0 or j == 0:
        return
    elif str1[i-1] == str2[j-1]:
        return 1 + get_substring(str1, str2, i-1, j-1)
    else:
        return max(get_substring(str1, str2, i, j-1), get_substring(str1, str2, j-1, i))

```

However, I need the longest common substring, not the longest common sequence of letters. I tried altering my code in a couple of ways, one being changing the base case to...

```
if i == 0 or j == 0 or str1[i-1] != str2[j-1]:
    return 0

```

But that did not work, and neither did any of my other attempts. 

For example, for the following strings...

```
X = "AGGTAB"
Y = "BAGGTXAYB"
print(get_substring(X, Y, len(X), len(Y)))

```

The longest substring is **AGGT**.

My recursive skills are not the greatest, so if anybody can help me out that would be very helpful.

Answer: 
You need to recurse on each separately. Which is easier to do if you have multiple recursive functions.

```
def longest_common_substr_at_both_start (str1, str2):
    if 0 == len(str1) or 0 == len(str2) or str1[0] != str2[0]:
        return ''
    else:
        return str1[0] + longest_common_substr_at_both_start(str1[1:], str2[1:])

def longest_common_substr_at_first_start (str1, str2):
    if 0 == len(str2):
        return ''
    else:
        answer1 = longest_common_substr_at_both_start (str1, str2)
        answer2 = longest_common_substr_at_first_start (str1, str2[1:])
        return answer2 if len(answer1) < len(answer2) else answer1

def longest_common_substr (str1, str2):
    if 0 == len(str1):
        return ''
    else:
        answer1 = longest_common_substr_at_first_start (str1, str2)
        answer2 = longest_common_substr(str1[1:], str2)
        return answer2 if len(answer1) < len(answer2) else answer1

print(longest_common_substr("BAGGTXAYB","AGGTAB") )

```
I am so sorry. I didn't have time to convert this into a recursive function. This was relatively straight forward to compose. If Python had a `fold` function a recursive function would be greatly eased. 90% of recursive functions are primitive. That's why `fold` is so valuable. 

I hope the logic in this can help with a recursive version.

```
(x,y)= "AGGTAB","BAGGTXAYB"
xrng=  range(len(x)) # it is used twice

np=[(a+1,a+2) for a in xrng] # make pairs of list index values to use

allx = [ x[i:i+b] for (a,b) in np for i in xrng[:-a]] # make list of len>1 combinations

[ c for i in range(len(y)) for c in allx if c == y[i:i+len(c)]] # run, matching x & y

```

...producing this list from which to take the longest of the matches

['AG', 'AGG', 'AGGT', 'GG', 'GGT', 'GT']

I didn't realize getting the longest match from the list would be a little involved.

```
ls= ['AG', 'AGG', 'AGGT', 'GG', 'GGT', 'GT']
ml= max([len(x) for x in ls])
ls[[a for (a,b) in zip(range(len(ls)),[len(x) for x in ls]) if b == ml][0]]

```

"AGGT"