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
``````