Suppose we want to count the number of times that a key string appears in a target string. We are going to create two different functions to accomplish this task: one iterative, and one recursive. For both functions, you can rely on Python's find function - you should read up on its specifications to see how to provide optional arguments to start the search for a match at a location other than the beginning of the string. For example,
find("atgacatgcacaagtatgcat","atgc")
#returns the value 5, while
find("atgacatgcacaagtatgcat","atgc",6)
#returns the value 15, meaning that by starting the search at index 6,
#the next match is found at location 15.
For the recursive version, you will want to think about how to use your function on a smaller version of the same problem (e.g., on a smaller target string) and then how to combine the result of that computation to solve the original problem. For example, given you can find the first instance of a key string in a target string, how would you combine that result with invocation of the same function on a smaller target string? You may find the string slicing operation useful in getting substrings of string.
