Definition: binary code is just a string of 0s and 1s.
'11100'
'01000011'
''
'0'
'1'
...
also called a binary string.

We're going to be given an integer r, and we want to generate all binary codes of length r.

def codes(r: int) -> List[str]:
    '''Return all binary codes of length r.




codes(2)... what are all of the binary codes of length 2?
['00', '01', '10', '11']
4 binary codes of length 2.

codes(1): all binary codes of length 1
['0', '1']

codes(0)... all binary codes of length 0
There is one binary string of length 0. ''
['']

codes(3)...
How many binary codes are there of length 3? 8
000 001 010 011 100 101 110 111

When solving a problem that uses recursion, CS experts rarely think about how recursion actually works inside the computer.
Abstraction

Imagine that you have a solution to a smaller version of the subproblem that you want to solve.

Let's say that you're trying to solve codes(3).
Imagine that you have a solution to codes(2).
Your goal is to solve codes(3) using that solution to codes(2).
Think about how to extend codes(2) to codes(3).

Someone gives us this...
['00', '01', '10', '11']

Look at the code '00'.
If we add a '0' to the end: '000'
If we add a '1' to the end: '001'
Using '00', we managed to generate 2 of our length-3 codes.

Length-2 codes: 4. Length-3 codes: 8.
If every length-2 code gives us 2 length-3 codes, with no overlap in the length-3 codes that we generate, then we're done.

Starting with '01' now...
If we add a '0' to the end: '010'
Add a '1' to the end: '011'

Let's start with '10':
Add '0' to the end: '100'
Add '1' to the end: '101'

Start with '11':
Add '0' to the end: '110'
Add '1' to the end: '111'

We generated all 8 codes of length 3. Each length-2 code gave us 2 length-3 codes.


Given any length r-1, we know how to solve the problem for length r.
You take every code of length r-1, and add a '0' to the end.
Then, take every code of length r-1 again, and add a '1' to the end.
That gives you all binary codes of length r.

The way that we obtain the smaller solution is through recursion.
Recursion: calling the function that's currently being defined, but with a smaller value.

Template for a recursive function has two parts...
1. One or more base cases
2. One or more recursive cases


def codes(r: int) -> List[str]:
    if r == 0:
        return ['']
    # r > 0
    smaller = codes(r-1) # smaller is a list of str
    result = [] # this will be all length-r codes
    for code in smaller: # code is a str
        result.append(code + '0')
        result.append(code + '1')
    return result