Free Recursion lessonsRecursion · Stage 3 · Include or skip · Step 2

Strings with no two 1s together

Count the binary strings of a given length with no two 1s side by side, by choosing the first character and recursing on what is left. About 13 minutes.

A rule changes what's left

How many strings of 0s and 1s of length n have no two 1s next to each other? For length 3 they are 000, 001, 010, 100 and 101. Not 011, 110 or 111.

Build a string from the front. If the first character is 0, anything valid can follow: that is the count for length n minus 1. If it is 1, the next character is forced to be 0, and after that anything valid can follow: the count for length n minus 2.

Starts with 0: the rest is any valid string one shorter.

Starts with 10: the rest is any valid string two shorter.

In code

def ways(n):
    if n < 0:
        return 0
    if n == 0:
        return 1
    return ways(n - 1) + ways(n - 3)

Counts for lengths 0 to 5.

leftright

Length 0: one string, the empty one.

Move 1 of 5

Small cases first

Make sure the smallest cases are right, since everything builds on them. Length 0 has one string, the empty one. Length 1 has two: "0" and "1".

With only these two base cases, every larger length reduces to them. For length 2, count(1) + count(0) = 2 + 1 = 3: "00", "01" and "10". The calls branch twice, so they multiply quickly, a limit we'll learn to fix with remembering later.

Two base cases: because the call reaches back by two.

Branching twice: makes many repeated calls for big n.

Quick check

A string starts with 1. What must come next, and why?

AA 0, because two 1s may not be side by side
BA 1
CEither

Show the answer

A 0, because two 1s may not be side by side. After a 1, only 0 is allowed, so the choice is forced.

Your problem

No two 1s together

Count the strings of length n made of the characters 0 and 1 in which no two 1s are next to each other. Use a recursive function.

Example

n = 3 → 5

0 ≤ n ≤ 27

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.