In the first two videos of this module, we introduced recursion using string as examples. However, we could have solved either of those problems with iteration. This video introduces a situation where recursion leads to a natural solution that is relatively difficult to find if you're stuck using loops.

The problem we'd like to solve is the binary string problem. In the binary string problem, you must generate all possible strings of length n composed of only 0's and 1's.

For example, consider strings of length 4. There are 16 strings that we must generate.

These are all of the possible ways of choosing each character to be a 0 or 1. In general, for a given number n, there are 2^n strings of 0s and 1s that we'd like to output.

At this time, I encourage you to pause the video and think about how you'd solve this problem iteratively. It's certainly possible, but I don't think there's an immediately obvious way of doing it. Remember that n can be any positive number, so you can't hard-code n nested loops in the code because you don't know the value of n.

Luckily, there is a natural recursive solution to this problem.

Let's start by looking for a natural base case. n equal to 0 is a good base case. It's the empty string. Or n equal to 1 -- which generates the strings 0 and 1.

Now, let's look at how to extend from a case we know how to solve to a larger case.

If we start at a base of n equal to 0, then to get to strings of length 1,

we need to append both a "0" and a "1" to the empty string. And to get from strings of length 1 to length 2,

we must, again, add both a "0" and a "1" to all of our length 1 strings. Let's apply that process to a larger case.

Imagine that we had a way of successfully outputting all strings of 0s and 1s of length 3.

When we append a 0 to each one, we get 8 strings of length 4. These are half of the strings that we want.

Now we get the other half by appending a 1 to each of the original strings.

So we have a way of generating all required strings of length n + 1, assuming that we know how to generate all strings of length n. We have a solution for n equal to 0. 0 gives us 1. 1 gives us 2. 2 gives us 3. And so on, so we have a solution to our problem. This is a *recursive description* of generating these strings, because the algorithm generates strings of length n by relying on the generation of strings of length n-1.

Let's take a look at one possible implementation of this recursive idea.

Our function has two parameters: bits is an array that we will fill with 0s and 1s and index is the position in the array that should be filled next.

Once the bits array has had N values placed in it, we print the binary number it represents.

Otherwise, we haven't generated a number of length N yet, so we add a bit and then recursively call the function to add more bits.

Here is the program operating on n equals 4. This problem, which is very difficult if you are limited to loops, is easily solvable if you look at it from a recursive perspective.