Follow Us On Twitter
Twitter

Computer Science in K-12

An A to Z Handbook on
teaching programming
BUY NOW

Introduction Video

Discussion Questions

Discussion Questions/Activities/Resources
  1.  Connect to real-world examples. Recursion is based on the idea of self-similarity. There are many examples of self-similarity in nature and the world around us. How can we leverage this idea in the classroom as a hook to orienting students to recursion?
  2. Fractals are a great visual representation and demonstration of self-similarity and recursion.
  3. Tracing Recursion. The chapter urges students to trust the recursion using the recipe for setting up the recursive call 🙂 However, it may be helpful (drawing on pedagogy ideas from Chapter 23) to use some simple examples to trace the recursion as a whole class activity or in small student groups.
    1.  Here is a PDF resource that traces code to draw a ‘Spiraling Turtle’ using recursion in Logo.
    2. Here is an example of a code snippet you can give to students formatively, to have them trace code to figure out the output (Source: UTeach Computer Science, UT Austin).

      Trace the following recursive call.  Show your code tracing work and indicate what is printed as a result of the call printMe(4) ?  

    public void printMe(int num)

    {

       if (num > 1)

       {

          printMe(num-1);

          System.out.print(num);

          printMe(num-1);

       }

    }

    (Solution)
  4. Our learning goals for various concepts vary by our context— the grade/age of our students, the learning setting, prior experience, etc. Which of the following learning goals related to loops do you address in your teaching? What pedagogy do you adopt to address these? Which ones are problematic for your students, and in what way? How do you address student difficulties?
    L0 Looping constructs involve repeating an instruction/command/block or a set of instructions/commands/blocks
    L1 A loop can run a fixed/pre-determined number of repetitions. This is a simple repeat loop.
    L1a Commands/constructs that achieve simple repetition (such as “Repeat”)
    L2 #2. All the commands (or blocks) within a loop repeat as a “unit” (not individually)
    L3 Loop structures can have code preceding and/or following it
    L4 Interpreting control flow that includes code before & after
    L5 Variables can control the number of fixed repetitions
    L6 One type of loop is a forever loop. With a forever loop, the actions in the body of the loop continue “endlessly”.
    L7 The sequence of commands within a loop matters
    L8 Loops can have conditionals within them (ability to trace such execution)
    L9 Loops can aggregate values (thus having a cumulative effect)
    L10 Loops can terminate based on an expression (evaluating to true or false)
    L10a Understanding how different commands/constructs can be used for such looping (for, while, repeat until, …)
    L10b Such loop-termination expressions can involve Boolean variables (AND, OR, NOT)
    L11 The loop condition is checked at that one point in the code and not at all times
    L12 Variables can be aggregated/updated within loops (using expressions)
    L12a A “loop-controlling” variable being updated in the loop is part of the loop termination expression
    L13 Loops can be nested (what necessitates such nesting? Examples)
    L13a How nested loops work (tracing)
    L14 Using loops to iterate through lists & arrays
    L14a Using loops to iterate through lists & arrays with variable updates within loops
    L14b Using loops to iterate through lists & arrays with conditionals within the loop
    L14c Using loops to iterate through lists & arrays with conditionals within the loop as well as variables updated within loop
  5. The following some known naive conceptions are related to understanding of loops. Which of these have you encountered in your teaching? Are there others? Design a lesson plan that explicitly tackles one of these, and also formatively checks if students are harboring these naive misconceptions? What pedagogies/strategies do you adopt?
    The expressions in a ‘while’ statement are continuously checked; the loop exits the instant the expression becomes false
    One looping construct is better than the other one (e.g., while-loops are better than for- loops) based on their familiarity with one type of loop or the order they learned loop constructs, rather than understanding that each looping construct has benefits for solving different problems
    A conditional statement inside a loop will be executed whenever the condition is true, even if this occurs outside of the loop

Additional Materials

Linear Recursion Case Studies

We’ve found it useful to show a series of examples with our students, with each example different in a small, subtle way from the previous one. These all have one recursive call, and make the problem smaller by one at each step, so they’re called linear recursion.

1. Length of a sentence

You’re given a sentence (in some languages, that means a string), and asked to compute the length. There’s a built-in utility for that, certainly, but by rewriting it, you can test it.

  • Divide: Cut off a letter
  • Invoke: Call yourself on the sentence that’s smaller by one letter
  • Combine: If you’re asked to find the length of “computer” and someone hands you the length of “omputer”, what will you do with it to find the length of computer? You just add 1 for the “c”, right?
  • Stop Dividing: We can stop with one letter (and return 1) or no letters (and return 0). We prefer the latter.

Snap!

Python

def my_length(sentence):

if sentence == “”:

return 0

else:

return 1 + my_length(sentence[1:])

2. Keep the As in a list of grades

You’re given a list of grades (e.g., A, C, F, D), and asked to return a new list in which you only keep the As. This is different from the first because it’s a list that stores our data, and because we don’t just do the same thing to every element. This is known as a filtering pattern, and Snap! provides keep and Python provides list comprehensions to do these as higher-order functions (HOFs) without having to write a routine ourselves!

  • Divide: Cut off the first list element
  • Invoke: Call yourself on the list that’s smaller by one element
  • Combine: If you’re asked to keep the As of (A B C A) and someone hands you a list of all As from (B C A), what will you do? You just add the first A to the answer, right? But what if you’re asked to keep the As from (F B C A) and someone hands you the same thing? You just return what they handed you (since you’re thankful you’re not including the F!). So there’s a choice to be made here.
  • Stop Dividing: Similar to the last problem, we prefer to stop with an empty list (and return the same empty list).

Snap!

Python

def keep_As(grades):

if grades == []:

return grades

else:

if grades[0] == “A”:

return grades[0:1] + keep_As(grades[1:])

else:

return keep_As(grades[1:])

Snap! HOF

Python HOF

>>> [grade for grade in [“A”,”B”,”C”,”A”] if grade == “A”]

[‘A’, ‘A’]

3. Did I get all As?

You’re given a list of grades (e.g., A, C, F, D), and asked to return True if it’s all As.

  • Divide: Cut off the first list element
  • Invoke: Call yourself on the list that’s smaller by one element
  • Combine: If you’re asked to see whether (A B C A) is all As and someone says (B C A) does NOT have all As, what will you do? You just say no, right? But what if you’re asked to see whether (A A … A) [imagine it’s a really big list] and someone says that (aside from the first one, which they didn’t check) is all As, what do you do? You check the first one to make sure it too is all As, and say yes. So there’s a choice to be made here.
  • Combine (alternate): But there’s another way to think of this problem. You can restate the problem as “I have all As if the first one is an A AND all the rest of them are As”. That way, there’s no choice.
  • Combine (clever): There’s a really cool way to take this one further. The entire problem can be rephrased  as “I have all As if the list is empty or (the first one is an A AND all the rest of them are As)” — this directly translates to code that doesn’t have the if-then-else standard pattern!
  • Stop Dividing: Similar to the last problem, we prefer to stop with an empty list. But what do we return here? Most students say False, but it’s True here because the question is better stated “was the list free from non-As”? Yes, an empty list has none of these grades, so True.

Snap!

Python

def All_As(grades):

if grades == []:

return True

else:

if grades[0] == “A”:

return All_As(grades[1:])

else:

return False

Snap! (alternate)

Python (alternate)

def All_As(grades):

if grades == []:

return True

else:

return grades[0] == “A” and All_As(grades[1:])

Snap! (clever)

Python (clever)

def All_As(grades):

return (grades == []) or (grades[0] == “A” and All_As(grades[1:]))

Assessments

Formative Assessments (Source: UTeach Computer Science, UT Austin)