CODEWITHSUNDEEP
python
Sc4r
Sc4r

Reputation: 700

A recursive version of a code

In determining if a string is a subsequence of another I have the following code:

def subseq(strA, strB):
    if not strA:
        return True
    else:
        for char in strB:
            if strA:
                strA = strA[char == strA[0]:]
    return strA == ""

>>> subseq('cat', 'XIKSLPWswifmscakst')
True
>>> subseq('cat', 'XIKSLPWswifmsctksa')
False

while this works fine, is there a way to solve this recursively?

Upvotes: 0

Views: 65

Answers (1)

utdemir
utdemir

Reputation: 27216

Iterative versions usually works better on Python, since it doesn't have tail call optimization, and function calls are heavy. But as an exercise, here is my solution.

def subseq(needle, haystack):
    if not needle: return True
    if len(needle) > len(haystack): return False
    if needle[0] == haystack[0]: 
        return subseq(needle[1:], haystack[1:])
    else: 
        return subseq(needle, haystack[1:])

But don't use this!

  • It'll cause stack overflow on long strings(len(s) > sys.getrecursionlimit()).
  • It'll build a lot of intermediate strings(Every slice returns another copy)
  • An iterative version is just as readable.

Upvotes: 1

Related Questions