Recursive function that determines if the first n characters in two different strings are the same-CodePudding

Here is the iterative solution:

def firstNCharsSame(string, string2, n):
    same = True
    for i in range(n):
        same &= string[i] == string2[i]
    return same

print(firstNCharsSame("apple", "appll", 5))# ->false
print(firstNCharsSame("aaaae", "appll", 5))# ->false
print(firstNCharsSame("apple", "apple", 5))# ->true

I am need to make a recursive function to do the same thing. I find recursion very confusing but here is my attempt.

def firstNCharsSame(string, string2, n):
    if n > 1:
        firstNCharsSame(string, string2, n-1)
    return string[n - 1] == string2[n - 1]

This effectively only checks if the last characters in the strings are the same. I need to & the all values returned by all the calls of this function like I have done in the iterative version but I am struggling to understand how I can access what the "inner(higher up the stack)" function returns from the "outer(lower down the stack)" function.

CodePudding user response：

You can use the base case as 0, and implement like so:

def firstNCharsSame(string, string2, n):
    if n == 0: 
        return True
    if n > min(len(string), len(string2)):
        return False
    return string[n - 1] == string2[n - 1] and firstNCharsSame(string, string2, n-1)

CodePudding user response：

You need to combine the recursive result with testing the current index.

def firstNCharsSame(string, string2, n):
    if n == 0: # base case
        return True
    if n > len(string) or n > len(string2):
        return False
    return string[n - 1] == string2[n - 1] and firstNCharsSame(string, string2, n-1)

CodePudding user response：

Maybe something like this:

def firstNCharsSameRec(string, string2, current, n):
    if current >= n:
        return True

    if string[current] != string2[current]:
        return False

    return firstNCharsSameRec(string, string2, current   1, n)

And calling it like this:

print(firstNCharsSameRec("apple", "appll", 0, 5))
print(firstNCharsSameRec("apple", "appll", 0, 3))

CodePudding user response：

You only need to use the last parameter as a decreasing counter. Just compare the first characters and recurse for the rest:

def firstNCharsSame(a, b, n):
    return not n or a and b and a[0]==b[0] and firstNCharsSame(a[1:],b[1:],n-1)