Be sure to read the SPECIFICATIONS carefully! And write comments!

Specifications and Notes $($for both parts$)$:

There should be no loops.

There should be no global variables $($i$.$e$.,$ no variables defined outside of all functions$).$

You are only allowed to use the header iostream.

You are not allowed to use sequences, vectors, or any advanced data structure that can store an

arbitrarily long collection of integers.

No input prompts or additional output should be used.

Use the provided templates for each part $-$ the template file includes code that receives input and

displays output from the function call on the input.

Note: Each problem has three visible test cases on Gradescope. You will see if your code passes these

three test cases. In addition, each has two invisible test cases, which you will not be able to see until

after grades are released $($you will not see if your code passed or did not pass these$).$ To receive credit,

the execution must produce the correct results on invisible test cases. Additionally, your program must

include comments that clearly and concisely explain the reasoning and structure of your program.

$2$a$)$ countValidBinaryWarmup.cpp

A binary string $($i$.$e$.,$ a string consisting of $0\text{'}$s and $1\text{'}$s$)$ is called $1-$separated if there is at least one

$0$ separating any two $1\text{'}$s$.$ For example, $10010$ is a $1-$separated binary string of length $5,$ whereas

$11000$ is not.

Write a recursive function oneSeparated to count the number of $1-$separated binary strings of a

given positive integer length. The function should have two parameters: the length of the string

and the ending number $(0$ or $1).$

You may assume that the input length will be a positive integer and the ending number will be

either $0$ or $1.$

Below are examples of what the function oneSeparated should return for the given input parameters.

oneSeparated $(1,1)$ should return $1$ since the binary string consisting of a single $1$ is $1-$separated.

oneSeparated $(3,1)$ should return $2,$ since the binary strings of length $3$ ending in $1$ that are

$1-$separated are $001$ and $101.$

oneSeparated $(3,0)$ should return $3,$ since the binary strings of length $3$ ending in $0$ that are

$1-$separated are $000,010,$ and $100.$

$2$b$)$ countValidBinary.cpp

This is a generalization of the previous part. Given a positive integer $k,$ we call a binary string

k$-$separated if there are at least $k0\text{'}$s separating any two $1\text{'}$s$.$ For example, for $k=2,$ and string

length $6,100100$ is a $2-$separated binary string, whereas $100101$ is not.

Note that k$-$separated means if there are more than two $1\text{'}$s$,$ then they must be separated by at

least $k0\text{'}$s$.$ So there need not be more than two $1\text{'}$s for the string to be k$-$separated. For example

$100$ is considered $1-$separated, $2-$separated, $3-$separated, and in fact, k$-$separated for any positive

integer $k.$

Write a recursive function kSeparated to count the number of k$-$separated binary strings of a given

positive integer length. The function should have three parameters: the value of $k,$ the length $n$ of

the string, and the ending number $(0$ or $1).$

You may assume that the input length and $k$ will be positive integers, and the ending number will

be either $0$ or $1.$

Below are examples of what the function kSeparated should return for the given input parameters.

For $k=2,n=3,$ kSeparated$(2,3,0)$ returns $3$ and kSeparated$(2,3,1)$ returns $1,$ since $000,010,$

$100,$ and $001,$ are the binary strings of length $3$ that are $2-$separated.

For $k=3,n=3,$ kSeparated$(3,3,0)$ returns $3$ and kSeparated$(3,3,1)$ returns $1,$ since the same

strings of length $3$ that are $2-$separated are also $3-$separated.

For $k=3,n=4,$ kSeparated$(3,4,0)$ returns $4$ and kSeparated$(3,4,1)$ returns $1,$ since $0000,0010,$

$0100,1000,$ and $0001$ are the binary strings of length $4$ that are $3-$separated.