In this tutorial, we will be understanding a very interesting problem known as **Forming a string with no consecutive 1s**. Let us first understand what do we want to achieve in this problem.

We have an integer **n** that is the size of the string i.e. the number of bits in the final string.

Our aim is to get the string having n bits with no consecutive 1 which means: ** 11 is illegal** in the string.

Now for any string, there can be two cases:

If the **first element is 0** then the next element can be either 0 or 1.

In the other case i.e. **the first element is 1** then the only choice we have for the next element is 0.

Our aim is to find the **count of all such possible strings which satisfy the condition** mentioned above.

## How to find the number of possible strings without consecutive 1s?

The problem can be solved in a manual way or through the recursion approach. The recursion approach is a better, more efficient, and faster technique to solve the problem.

If you want to know more about recursion read the tutorial mentioned below.

*Read more about Recursion: Recursion in Python*

The two cases are as follows:

**First digit is 1**then we**set the second bit as 0**and check for**n-2**places left in the final string.**First digit is 0**then we check for**n-1**places left in the string

First, let us look at the answer for lower values of n starting from 0.

Value of n | No. of possible strings |

0 | 0 |

1 | 2 ( 0,1) |

2 | 3 (00,01,10) |

For all the cases where n is greater than 2, we will be considering the two cases.

## Implementing the Recursion in Python

```
def count_no_ways(n):
if(n==0):
return 0
if(n<3):
return n+1
return count_no_ways(n-1) + count_no_ways(n-2)
n = int(input())
print(count_no_ways(n))
```

**Output:**

10

144

I hope by end of this tutorial, I hope you understood the problem, solution, and code implementation of the solution.

Thank you for reading! Happy learning! 😇