Week 05 · Wednesday: Loop or recursion? (Code Crew G5)

Wednesday: Loop into recursion

Rocket has a loop that prints every star in the catalog. Raven dares him to rewrite it with recursion.

"Easy!" Rocket says. Then he stares at the screen. "Um, where do I start?"

Raven smiles. "What do you notice about the loop? When does it stop, and what changes each pass?"

"It stops when there are no stars left," Rocket says. "Each pass handles one star."

Nova blinks. "Here is a hint. Those two answers are your base case and your smaller step."

Three questions to convert a loop

When does the loop stop? That becomes the base case.
What gets smaller each pass? That becomes the smaller step.
What work happens in one pass? Do it once, then make the smaller call.

def show_all_loop(items):
    for item in items:
        print(item)

def show_all(items):
    if items == []:
        return
    print(items[0])
    show_all(items[1:])

show_all_loop(["Ember", "Frost"])
show_all(["Ember", "Frost"])

Output:
Ember
Frost
Ember
Frost

Question	Answer for show_all
When does it stop?	When the list is empty: items == []
What gets smaller?	The list loses its first item: items[1:]
Work in one pass?	print(items[0])

PUT THE LINES OF COUNT_ITEMS IN ORDER. IT COUNTS THE ITEMS IN A LIST WITH RECURSION.

? if items == []:
? return 1 + count_items(items[1:])
?print(count_items(["Ember", "Frost", "Glow"]))
? return 0
?def count_items(items):

WHY THIS EXERCISEThe base case must be checked first, so an empty list stops before anything else runs.

What does the count_items program print?

WHY THIS EXERCISEcount_items adds 1 for each item, just like a loop that counts with count = count + 1.

CONVERT THIS LOOP: FOR G IN GLOW: TOTAL = TOTAL + G.

Read the question.
Tap your answer.

What is the base case for the recursion version?

What is the smaller step?

Practice lab: shout it out

def shout_loop(words):
    for w in words:
        print(w + "!")

def shout(words):
    if words == []:
        return
    print(words[0] + "!")
    shout(words[1:])

shout(["go", "now"])

What kind of list is the base case in shout?

How many lines does shout(["a", "b", "c"]) print?

What does shout(["hi"]) print?

How many calls does shout(["go", "now"]) make, counting the first?

CONVERT CHECK

Read the question.
Tap your answer.

Which line is the smaller step in shout?

Which line is the work of one pass?

Suppose shout called shout(words) without the slice. What happens?

Statement	True or false?
shout_loop and shout print the same lines.	?
shout_loop has a base case.	?
In shout, the base case is checked before the print.	?
words[0] is the first word in the list.	?

WHY THIS EXERCISEThe loop runs out of items. The recursion reaches the empty list.

What does count_items(["a", "b", "c", "d", "e"]) return?

WHY THIS EXERCISEcount_items adds 1 per item and 0 for the empty list.

Pick a loop you know. Answer the three questions to turn it into a recursion.

You converted a loop like a pro! Tomorrow we go the other way and turn recursion into a loop.