pythonpython-3.xrecursion

Identifying pattern and code for this problem


I found this problem and I'm trying to come up with a solution for it, but I'm not getting the pattern here. Any advice on how to approach it? (I want to understand what the pattern is and a suggestion on how to approach the solution). Thanks!


In this problem, you are asked to implement a function pattern(k) which given an integer k ≥ 0, returns a string as shown in the below examples. Guess the pattern for k ≥ 6. You are advised to use recursion.

Test Program:

for k in range(0,6):
    print("pattern("+str(k)+"): " + pattern(k))

Output:

pattern(0): 1
pattern(1): 1
pattern(2): 1001
pattern(3): 10010001
pattern(4): 1001000100001001
pattern(5): 10010001000010010000010010001

I didn't understand the pattern to begin with it properly. Perhaps a simple explanation can allow me to write up some sample code that might work.


Solution

  • In recursion, a function needs a termination condition and otherwise calls itself.

    The termination condition looks like: if k < 2: return '1'

    Now look for recurring patterns.

    • pattern 2 has at most 2 zeros
    • pattern 3 has at most 3 zeros
    • pattern 4 has at most 4 zeros
    • pattern 5 has at most 5 zeros

    It looks like '0'*k is part of the pattern.

    • pattern 3 looks like it starts with pattern 2.
    • pattern 4 looks like it starts with pattern 3.
    • pattern 5 looks like it starts with pattern 4.

    Also:

    • pattern 3 ends with pattern 1
    • pattern 4 ends with pattern 2
    • pattern 5 ends with pattern 3

    The recursive function looks like pattern(k-1) + '0'*k + pattern(k-2).

    Let's try it:

    def pattern(k):
        if k < 2:
            return '1'
        return pattern(k-1) + '0'*k + pattern(k-2)
    
    for k in range(7):
        print(f'pattern({k}): {pattern(k)}')
    

    Output:

    pattern(0): 1
    pattern(1): 1
    pattern(2): 1001
    pattern(3): 10010001
    pattern(4): 1001000100001001
    pattern(5): 10010001000010010000010010001
    pattern(6): 100100010000100100000100100010000001001000100001001