In the last video, we looked at three ways to print each character in a string. The last of these, a recursive solution, solved the problem by handling a small piece and then calling itself to handle the rest of the problem. In this video, we'll expand on this idea and then use it to solve another example.

Here is a recursive definition of a string. Rather than viewing a string as a sequence of characters, we view it as either a null character or a single character followed by a string.

In the previous example, we dealt with each part of this definition separately.

Here's the solution from the last video.

If the string matches our first case -- a NULL character -- then we're done. We've printed everything we can see.

If the string matches our second case, then we print a single character

and then call a function that handles strings. That function happens to be the one we just finished defining.

Let's apply that logic to a new problem.

Let's write a function that prints a string backwards.

#include <stdio.h>


void print_backwards(char *s) {

}


int main(void) {
    char *s = "violets are blue";
    print_backwards(s);
    return 0;
}
]
Here's a skeleton for our solution.

Let's handle the cases in turn.

If the string is empty, then we're done.

Here's the tricky part. We want to print the rest of the string before our single character.

So we'll handle the rest of the string first.

And then print the single character.

Success! But are you convinced that it works?

The reason why we can assume that recursive calls work correctly is closely tied to an idea called mathematical induction. Whether you're familiar with mathematical induction or not, my goal now is to convince you that the function really is correct.

It's pretty easy to see that the function works correctly for the empty string. If the string is empty, there's nothing to print. This is our *base case* -- the simplest case. One that doesn't rely on any recursive calls.

Now, does the function work correctly for a string consisting of a single character? In that case, we'd call our function on the empty string. Here's the trick: *we know that works*.  And then we'd print the character. We know that works, too -- our only character is now being printed last, so the string has been printed backwards.

Now what about longer strings? If you give me a string of length 2,

then I call my function on a string of length 1: *and we know that works*.

Then, I print the first character of my string last -- so the string has been printed backwards.

And in general, if you give me me a string of length n + 1, where I've already demonstrated that a string of length n is printed correctly,

then I call my function on a string of length n: *and we have established this works*.

And then I print the first character last. So the function works for strings of length n + 1.

Let's review. If I want to write a recursive function -- or prove to myself that one works -- then I should

Verify that the function works on small values like 0 or the empty string or whatever makes sense for the function under consideration.


Then, you can use the correctness on those small values to argue for the correctness of larger and larger values, until you are convinced that the function works in the general case.