• recursion is just when you have a method that calls itself! each call in the method does a small amount of work until all of those little small chunks of work add up to get your final solution!
• lets do an activity to find out all of the students names in a class
  • iterative version: 1 student(me) can go through each student and print out their name
    • which idea is this mechanism similar to? this idea that we just keep going trorugh all students iteratively and printing each of their name until we reach the size of the class?
    • write the loop on board
  • ok! now lets try simulating a recursive version of this! So each person will do a small amount of work to help us figure out how many people are in here!
    • each person says their name when I point to them, so each of you do a small amount of work instead of 1 person doing all of the work!
    • this saves you time as you dont have to worry about knowing EVERYONES name, you can just expect that everyone will do a bit of work by saying their name out loud and that way at the end we will have the names of everyone!
• explain stack
• explain stack over flow error (think of it like an infinite loop that will blow up your program)
• talk about how to prevent the risk of stack overflow
  • need an exit strategy so the method stops calling itself at some point
  • this is what we call a base case! a base case is a condition in your method, where the method can successfully return WITHOUT making another call to the method!
  • this is the condition our recursive calls eventually need to hit, so that it can return without going into recursion forever.
  • within your recursive calls, you need to be making progress towards your base case with every call, or every time the method recurses! if your code just keeps making calls without getting closer and closer to the base case, then the base case is useless cause you are never going to reach it and your program will again crash.
  • you can still run into problems even if you are making progress towards the base case, bc maybe you are just making wayyyy too many calls like 100,000 students.

why recursion?

• less code!
• new perspective (it is a whole new way of thinking)
• we are going to be learning about new data structures soon that NEED recursion!
• it is possible to have multiple base cases and recursive cases! but for now we will just focus on code with 1 base case and 1 recursive case
• Any time a recursive call is made, Java stops all operations on its current method and goes to work on the method that you just called.

mystery:

• show different possible visual representations since everyones brain works different
• im going to record the same problem for each of the 3 representations and I will give you guys the time stamp so you CAN SKIP TO WHICHEVER REPRESENTATION WORKS BEST FOR U!
• you can also give me feedback for which representations you guys would like to see in class more!
• problems
  • mystery1 (all)
  • mystery2 (all)
  • mystery3 (first 3)
  • mystery4 (first 3)
  • mystery5 (1 & 4)