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

- Python Jinja2 LaTeX Table
- Getting attributes of a class
- How can I print many significant figures in Python?
- How to allow list append() method to return the new list
- Calculate Last Friday of Month in Pandas
- Python type hint for Iterable[str] that isn't str
- How to iterate over a list in chunks
- How to exit the entire application from a Python thread?
- Running shell command and capturing the output
- How do I pass a variable by reference?
- Convert range(r) to list of strings of length 2 in python
- How can I get the start and end dates for each week?
- how to use send_message() in python-telegram-bot
- Python conditional replacement based on element type
- How can I count the number of items in an arbitrary iterable (such as a generator)?
- Find longest consecutive range of numbers in list
- Insert text in braces with asyncpg
- How does one put a link / url to the web-site's home page in Django?
- How to determine if a path is a subdirectory of another?
- Custom Keybindings for Ipython terminal
- FastAPI asynchronous background tasks blocks other requests?
- How to make sure that information from one file is duplicated into several text documents, without specific lines
- Installing a Python environment with Anaconda
- sklearn pipeline model predicting same results for all input
- Brew command not found after installing Anaconda Python
- How to get an XPath from selenium webelement or from lxml?
- Pipe PuTTY console to Python script
- How to align the axes of a figure in matplotlib?
- Persist ParentDocumentRetriever of langchain
- How to reset index in a pandas dataframe?