Write a recursive method that has one integer parameter (n) and returns the numb

Question

Write a recursive method that has one integer parameter (n) and returns the number of binary strings of length n that do not have two consecutive 1's. You should not use any loops in your solution. For example, for n = 4, the number of binary strings of length 4 that do not contain two consecutive 1's is 8:
0000,0001,0010,0100,0101,1000,1001,1010
For this problem, your method needs to return only the number of such strings, not the strings themselves.
HINT: The number of such strings is the number of strings that start with a 0 plus the number of strings that start with 10.

Explanation / Answer

public int numStrings(int n)
{
// break cases
if(n == 0) // 1 string of length 0
return 1;
if(n == 1) // 2 strings: 1 and 0
return 2;

// The number of such strings is the number of strings that start with a 0 plus the number of strings that start with 10.
return numStrings(n-1) + numStrings(n-2);
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.