Tic-Tac-Toe : Recursion

# Tic-Tac-Toe - Session 2 ## Objective: By the end of the lesson, you will: * learn a new way to work with lists and other data structures; and * build the intuition needed to make progress on our tic-tac-toe solver. ## Colab Link Here is today's colab [link.](https://colab.research.google.com/drive/1xqdxWfj3ueJ7QoE47eu868Brq4sfkX9R#scrollTo=FK8K5OaZT53s) ## A Task Let's start by defining a list of names: ```python = mosaic_staff= ["Muhiim", "Kamryn", "Dior", "Nicole", "Mel", "Tim"] ``` Suppose that we wanted to print out every string in this list, in order. How would you do that, based on what you already know? <details> <summary> Think 💡, then click. </summary> We know how to use `for` loops. Maybe we can write something like this? (I'm going to use letters to label different implementations for this task, hence the "a" at the end of the function name.) ```python= def print_names_a(names): for name in names: print(name) print_names_a(mosaic_staff) ``` </details> ## Another Approach A `for` loop works very well. Today we're going to learn another way to break down this problem. It might look a little strange at first, but the idea will be very important for writing our tic-tac-toe game. So, how can we perform the same task without using any *loops*? The core challenge is that we still need to write code that works for lists of arbitrary length---we can't get away with something like: ```python= if len(names) > 0: print(names[0]) if len(names) > 1: print(names[1]) # ... ``` If we did this, there'd always be a limit to how many names the program would print; we'd have to stop writing lines of code at some point! We need to somehow manage to do what loops do, without using `for` or `while`. Let's slightly change the problem statement. Suppose we already knew how to print out all the names in a list *starting at some index*, and we had already written a helper function for this called `print_names_starting_at`. What would our function look like, given that it could call that helper? <details> <summary> Think 💡, then click. </summary> Printing the whole list would just mean starting at index 0, so: ```python= def print_names_b(names): print_names_starting_at(names, 0) ``` </details> Now we only have to write `print_names_starting_at`. At first, it might look like we've complicated the problem. In fact, this is just the kind of added structure we can use. Yes, keep things simple whenever possible, but don't be afraid to change your perspective. We're going to solve this slightly re-worded problem, and then use it to solve the original task (using the code in the answer above). Let's start writing and see where we get. We're going to use just three tools. Think about how we might use them together, and then try it out. Keep in mind: **We're not trying to solve the problem perfectly yet!** It's ok to build a function that solves the problem of unknown list length, but might crash or do something else undesireable along the way. Make incremental progress. The tools are: * calling functions; * printing out the string at some list index; and * arithmetic. Here's the function template: ```python= def print_names_starting_at(names, idx): pass ``` What can we do? <details> <summary> Think 💡, then click. </summary> Maybe something like this. After all, a function can call a function. That includes calling itself! (If you haven't heard the term before, this is called *recursion*): ```python= def print_names_b(names): print_names_starting_at(names, 0) def print_names_starting_at(names, idx): # print the next name we have to print: print(names[idx]) # ...and then print the *rest* of the names: print_names_starting_at(names, idx+1) print_names_b(mosaic_staff) ``` Think of this like a chain of tasks: * print the name at 0 and then * print the name at 1 and then * print the name at 2 and then ... </details> This doesn't quite work yet. Try it out---what happens? How can you fix the problem? **In class, we'll step through how this works using either `print` statements or a debugger.** <details> <summary> Think 💡, then click. </summary> The problem is that the program doesn't know when to stop. It keeps trying the next index, incrementing until it "falls off" of the end of the list and the program crashes. So let's add a guard against that: ```python= def print_names_b(names): print_names_starting_at(names, 0) def print_names_starting_at(names, idx): # Stop when we're asked to print a name farther into the list than exists: if idx >= len(names): return # Otherwise do what we did before: print(names[idx]) print_names_starting_at(names, idx+1) print_names_b(mosaic_staff) ``` In computer science, you'll often see these two cases ("stop here" and "keep going") referred to as the *base case* and *recursive case*. </details> Looking at the code, it's much more complicated than just a `for` loop. Probably, given this task, I'd use a `for` loop. But it's a good way to introduce a general concept---recursion---that is incredibly valuable in other settings... ...like building a program to play tic-tac-toe. ### Another Version Let's use recursion in a different way to solve the same problem. Let's say that, rather than "print all the names starting from this index" we wanted to get rid of the extra parameter. Could we use recursion without introducing the helper at all? Here's the template: ```python= def print_names_c(names): pass ``` Hint: we're still using recursion, so `print_names_c` should call itself. <details> <summary> Think 💡, then click. </summary> We've got to change the list being passed to successive calls. There are two ways we could do this: * remove the first element from the list before each call; or * manufacture a new list, one element shorter each time, for every call. </details> What do you think the relative merits of each of these are? <details> <summary> Think 💡, then click. </summary> If we modify the list itself, then we'd never be able to get those names to use again in another context. (Consider: what if I wanted to print all the names out *twice*? If I removed names from the original list, I'd be out of luck...) So let's create a new list every time: ```python= def print_names_c(names): if len(names) == 0: return # stop when no more names to print print(names[0]) # Python shorthand for "everything but the first element" print_names_c(names[1:]) print_names_c(mosaic_staff) print(mosaic_staff) ``` We can verify that the original list, `mosaic_staff` is still populated by printing it out after calling the function, as above. </details> ### Optional: Note on Efficiency Looking at that last program, you might wonder about its efficiency. Performance is very subtle question, and you'll learn more about why as you take more computer science. For now, please keep in mind the following: * these examples (especially the final one) are built for the classroom, not efficiency; * lots of real problems (like the one we're about to tackle) are much easier to think about and implement using recursion; * it's more important for the program to *work* than to be *fast*; and * efficiency is complicated by the specifics of your program and how things work in the language you're using. By the way: if you *didn't* wonder about efficiency, that's just fine. You're not missing something important; I added this section to address questions I hear sometimes. ## Connecting this to tic-tac-toe Back to tic-tac-toe. **What data structure do we want to use to represent a board?** <details> <summary> Think 💡, then click. </summary> There are many, many options. Most of them work great. For this module, we'll be using a nested list to represent the board because you've all seen and used nested lists, and it will turn out to be convenient next time. </details>