← Back to the Introduction to Computer Science outline The Course Maker
← Introduction to Computer Science outline
Week 14 · Chapter

Chapter 14 — Recursion

Introduction to Computer Science Free sample edition

The module's primary reading · ~40–50 minutes · Objective 8 (implement and trace linear search, binary search, and selection sort; describe how an algorithm's step count grows with input size in Big-O terms; write and trace a simple recursive function; and define a class with init, attributes, and methods) and Objective 5 (define and call functions with parameters, arguments, and return values, distinguish return from print, and reason correctly about local and global scope) · Read it first this week; the lecture, the slides, the tutorial, the quiz, and the Coding Lab all build on it.

In plain language

Some jobs are easier to describe as a smaller copy of themselves. Counting down from 3 is saying 3 and then counting down from 2. This week you learn recursion (a way of solving a problem by having a function call itself on a smaller copy of the same problem). Every recursive function needs a place to stop, and you will see what happens when one is missing. As always, you predict what each program prints and then run it to check.

Why you already care about this

Picture the start of a school fun run. The starter calls out 3, then 2, then 1, then shouts Go! Nobody needs a list of every number to do that. Each number is followed by "count down from one less," and the shouting of Go! is what ends it.

Or picture opening a folder on a shared drive for a campus club. Inside are a few files and two more folders. Inside one of those folders are more files and another folder. To count every file, you count the files in front of you and then do the same job on each folder inside. The job contains a smaller copy of itself.

Your reading log is in this chapter too. In Week 9 a for loop added up the daily list [12, 40, 25, 0, 33, 17, 27] and printed 154. This week a function adds up the same list by adding the first day to the total of the rest, and it gets the same 154. You will see how it works, where it stops, and how to check a chatbot that claims to know.

By the end of this chapter you will be able to:

  • name the base case and the recursive case of a recursive function;
  • write and trace factorial(n) and say what each call returns;
  • predict the order of the printed lines as the call stack piles up and unwinds;
  • solve one problem by recursion and by a loop, and show by running both that the answers match;
  • sum a list recursively, with a base case on the empty list;
  • explain why a missing base case, or a call that does not shrink its input, raises RecursionError.

Carry this line with you: every call needs a smaller input — and somewhere to stop.

Where we are

  • Already covered: Week 5 gave you while loops and the infinite loop that never stops. Week 6 gave you for loops over range(). Week 7 gave you functions, return, None, local variables, and the frame Python Tutor draws for each call. Week 9 gave you lists and slices, and Week 13 gave you binary search and its halving.
  • This week: recursion, the base case and the recursive case, factorial, the call stack piling up and unwinding, recursion versus iteration, a recursive sum of the reading log, and RecursionError.
  • How they connect: a recursive call is an ordinary function call from Week 7, so it gets a frame with its own local variables. A missing base case is the recursion version of the Week 5 infinite loop.
  • Where we're going next: Week 15 introduces classes and objects, the last new idea of the course; a class bundles data with the functions that work on it.

Three earlier ideas carry most of the weight. From Week 7, every call opens a new frame, and a variable made inside a function is local to that call. From Week 7 again, return hands a value back to the caller, while a function that only prints hands back None. From Week 9, a slice such as daily[1:] builds a new, shorter list and leaves the original alone. Spend extra time on Sections 4 and 5. The quiz leans on both, and so does the Coding Lab.

1. Meet a function that calls itself

You have called one function from inside another since Week 7. Nothing stops a function from calling itself. The fun-run starter does exactly that: to count down from 3, say 3 and then count down from 2.

Recursion is a way of solving a problem in which a function calls itself on a smaller copy of the same problem, again and again, until the problem is small enough to answer at once.

A recursive function is a function whose body contains a call to itself, such as factorial, which hands back n times the factorial of n − 1 for any n above 0.

A recursive call is a line inside a function that calls that same function, such as the call to countdown with n minus 1 inside countdown; each recursive call opens a new frame of its own.

Worked example — the pinned countdown. Predict every line before you read the output.

def countdown(n):
    if n == 0:
        print("Go!")
        return
    print(n)
    countdown(n - 1)

countdown(3)

Output

3
2
1
Go!

Here is the trace, one call at a time.

  1. countdown(3): 3 is not 0, so it prints 3 and calls countdown(2).
  2. countdown(2): it prints 2 and calls countdown(1).
  3. countdown(1): it prints 1 and calls countdown(0).
  4. countdown(0): now n == 0 is True, so it prints Go! and returns.

In words: the run printed four lines, and Go! came last, because the call that prints it is the last call to start.

Misconception check. Students often think countdown(3) prints Go! first, because Go! sits near the top of the function body. That is tempting, because Python reads a program from the top down. But the if test sends only the call with n == 0 to that line, and that call starts last. The cure: trace one call at a time and write down what each call prints before it makes the next call.

In practice (your tools). Open your free browser Python runner, paste the countdown program, and press Run. Then change the last line to countdown(5) and predict the output before you run it again.

Memory hook: same job, smaller input — not the same call again.

2. Give it two parts: the base case and the recursive case

A set of nesting dolls opens down to one solid doll that does not open. That solid doll is what lets you finish. A recursive function needs the same thing: an input it answers without opening anything else.

The base case is the part of a recursive function that answers without calling the function again, such as returning 1 when n == 0; it is what lets the chain of calls stop.

The recursive case is the part of a recursive function that calls the function again on a smaller input that moves toward the base case, such as the call to factorial with n minus 1 inside factorial.

In countdown, the base case is the if n == 0: block, which prints Go! and returns. The recursive case is the last two lines, which print n and call countdown(n - 1). Every call moves n one step closer to 0, so the base case is always reached.

Worked example — start at the base case. Call the countdown with 0 and predict the output.

def countdown(n):
    if n == 0:
        print("Go!")
        return
    print(n)
    countdown(n - 1)

countdown(0)

Output

Go!

The base case ran at once and the run printed only Go!. No recursive call happened. That is the job of a base case: it is an answer that needs no more calls.

Misconception check. Students often think a small input needs no base case, because a countdown from 3 ends after a few steps. That is tempting, because the human starter knows to stop. But the computer does exactly what you wrote, not what you meant: without the if n == 0: block, nothing tells it to stop at 0, and it would carry on to −1, −2, and beyond. The cure: before you write the recursive case, write the base case and ask "which call answers without calling again?"

In practice (your tools). In your browser runner, call countdown(1) and predict the two lines. Then find the line of code that printed each one.

Memory hook: base case first; it is the floor the calls land on.

3. Build a value on the way back: factorial

A playlist of five songs can play in many orders. The first slot can hold any of 5 songs, the second any of the 4 left, then 3, then 2, then 1. Multiply them and you get 5 × 4 × 3 × 2 × 1 = 120 orders. That product has a name.

The factorial of n is the product of every whole number from 1 up to n, so 5 factorial is 5 × 4 × 3 × 2 × 1 = 120; 0 factorial is 1 by definition, which makes it a natural base case.

Look at the product again: 5 factorial is 5 times 4 factorial. Every factorial holds a smaller factorial inside it. That is the recursive case, and 0 factorial is the base case.

Worked example — the pinned factorial. Predict both lines.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(5))
print(factorial(0))

Output

120
1

factorial(0) went straight to the base case and returned 1. factorial(5) could not answer at once. It asked for factorial(4), which asked for factorial(3), and so on down to factorial(0). Then the answers came back up: 5 × 4 × 3 × 2 × 1 = 120, and the base case supplied the final 1. Section 4 shows those answers coming back one at a time.

Misconception check. Students often think 0 factorial should be 0, because multiplying by zero gives zero. That is tempting, because 0 is the number in the base case. But 0 factorial multiplies no numbers at all, and it is 1 by definition. If the base case returned 0, every product above it would be 0 too. The cure: check a base case by asking what it must be for the next call up to come out right; factorial(1) must be 1 × factorial(0), so factorial(0) must be 1.

In practice (your tools). In your browser runner, add the line print(factorial(3)) and predict it first. Then work out 3 × 2 × 1 by hand and compare.

Memory hook: the value is built on the way back up, not on the way down.

4. Watch the call stack pile up and unwind

A cafeteria keeps clean trays in a pile. You put a tray on top, and you take one off the top, never from the middle. Python keeps its unfinished calls the same way.

The call stack is the pile of frames Python keeps for the calls that have started and not yet returned, with the newest call on top; a call adds a frame and a return removes it.

A frame, from Week 7, is the box of local variables one call owns. So factorial(5) and factorial(4) each have their own n, one holding 5 and one holding 4. Nothing is overwritten.

Worked example — the pinned call-stack trace. This version of factorial prints a line when each call starts and a line when each call returns, indented by how deep the call is. The extra depth value only sets the indentation, and you can ignore it otherwise.

def factorial(n, depth=0):
    print("  " * depth + "call factorial(" + str(n) + ")")
    if n == 0:
        print("  " * depth + "return 1")
        return 1
    result = n * factorial(n - 1, depth + 1)
    print("  " * depth + "return " + str(result))
    return result

print(factorial(5))

Output

call factorial(5)
  call factorial(4)
    call factorial(3)
      call factorial(2)
        call factorial(1)
          call factorial(0)
          return 1
        return 1
      return 2
    return 6
  return 24
return 120
120

Read the output in two halves.

  1. The first six lines are the stack piling up: six calls, for n = 5, 4, 3, 2, 1, and 0. Each one waits for the call below it.
  2. The next six lines are the stack unwinding. factorial(0) returns 1. Then factorial(1) works out 1 × 1 = 1, factorial(2) works out 2 × 1 = 2, factorial(3) works out 3 × 2 = 6, factorial(4) works out 4 × 6 = 24, and factorial(5) works out 5 × 24 = 120.
  3. The last line, 120, is the print at the bottom of the program showing the value that came back.

In words: six calls went down and six returns came back, in reverse order, 1, 1, 2, 6, 24, 120.

The countdown has a call stack too. When countdown(0) is running, the calls for 3, 2, and 1 are still waiting underneath it, so four frames are open at the deepest level.

Misconception check. Students often think each recursive call overwrites n, so by the end there is only one n left, holding 0. That is tempting, because the same name n appears in every call. But each call has its own frame, and n is a local variable inside that frame, exactly as in Week 7. The cure: when you trace, keep one column per call, and never cross out an earlier call's n.

In practice (your tools). Paste the pinned factorial program into Python Tutor at pythontutor.com and click Next again and again. A new frame appears for each call, each with its own n. When factorial(0) returns, watch the frames disappear from the top down, each one carrying its return value.

Memory hook: frames pile up on each call and come off on each return.

5. Read what runs after the call: unwinding and return values

Think of leaving a trail of notes as you walk down a staircase, one note per step, and reading them on the way back up. The notes you read going up come in the opposite order to the steps going down.

Unwinding is the second half of a recursion, when the deepest call returns first and each waiting frame in turn finishes its remaining lines and returns to the call below it on the stack.

Worked example — move one line. This is the countdown with print(n) moved below the recursive call. Predict all four lines.

def countup(n):
    if n == 0:
        print("Go!")
        return
    countup(n - 1)
    print(n)

countup(3)

Output

Go!
1
2
3

Each call now makes its recursive call first and prints its n afterward. So no number is printed until the base case has printed Go!. Then the frames unwind: the call with 1 prints 1, the call with 2 prints 2, and the call with 3 prints 3. One moved line reversed the order.

Worked example — print is not return. The countdown prints, but it never returns a value. Predict all five lines.

def countdown(n):
    if n == 0:
        print("Go!")
        return
    print(n)
    countdown(n - 1)

result = countdown(3)
print(result)

Output

3
2
1
Go!
None

The first four lines come from inside the calls. The fifth comes from print(result). The call countdown(3) runs off the end of its body without returning a value. That hands back None, the Week 7 value a function returns when it gives back nothing else, and the bare return in the base case hands back the same None. So result holds None. factorial is different: its return n * factorial(n - 1) hands a number back to the call waiting below it, and that is how the 120 was built.

Misconception check. Students often think a recursive function that prints the right numbers also returns them, because the numbers appear in the output. That is tempting, because Week 7's return versus print mix-up looks the same here. But printing sends text to the output, and only return sends a value back to the caller. The cure: ask of every recursive function, "what does each call hand back?" and test it with print(result).

In practice (your tools). Paste countup into Python Tutor at pythontutor.com and step until the Go! line runs. Count the frames still waiting, then keep stepping and watch each one print its number as it comes off the stack.

Memory hook: lines before the call run going down; lines after the call run coming back.

6. Solve it both ways: recursion versus iteration

You can climb a staircase by counting steps in a loop, or by saying "one step, then climb the rest." Both get you to the top. Recursion and loops have the same relationship.

Iteration is repeating a block of code with a loop such as for or while, as opposed to repeating work by having a function call itself; a problem solved both ways gives the same answer.

Worked example — the pinned sum, two ways. sum_to(n) adds the whole numbers from 1 to n by recursion, and sum_to_iter(n) adds them with a for loop. Predict all three lines.

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

def sum_to_iter(n):
    total = 0
    for i in range(1, n + 1):
        total = total + i
    return total

print(sum_to(5))
print(sum_to_iter(5))
print(sum_to(100))

Output

15
15
5050

Both versions print 15 for 5, since 1 + 2 + 3 + 4 + 5 = 15. The recursive one says "5 plus the sum up to 4," and its base case says the sum up to 0 is 0. The loop one keeps a running total, the accumulator from Week 5, and uses range(1, n + 1) so that n itself is included. The recursive sum_to(100) prints 5050.

Worked example — factorial with a loop. The same switch works for factorial.

def factorial_iter(n):
    product = 1
    for i in range(1, n + 1):
        product = product * i
    return product

print(factorial_iter(5))
print(factorial_iter(0))

Output

120
1

The loop version prints 120 and 1, matching the recursive factorial. For factorial_iter(0), range(1, 1) is empty, so the loop body never runs and product stays 1, the same answer the base case gave.

Misconception check. Students often think recursion and iteration give different answers, because the two programs look so different. That is tempting, because one has a loop and the other has none. But both carry out the same arithmetic, and the runs above print the same 15 and the same 120. The cure: when you write a recursive function, write the loop version too and run both on a few inputs.

In practice (your tools). In your browser runner, add print(sum_to_iter(100)) and predict it before you run it.

Memory hook: a loop and a recursion can walk the same road.

7. Sum the reading log recursively

A teacher passing a stack of quiz papers down a row says, "Count yours, add it to the count from everyone behind you." The last student, with no one behind, says zero. The row adds itself up.

Worked example — the reading log's Week 14 stage. The empty list is the base case. Otherwise, the total is the first day plus the total of the rest. Predict both lines.

def total_pages(daily):
    if daily == []:
        return 0
    return daily[0] + total_pages(daily[1:])

print(total_pages([12, 40, 25, 0, 33, 17, 27]))
print(total_pages([]))

Output

154
0

The first line is 154, since 12 + 40 + 25 + 0 + 33 + 17 + 27 = 154, the same total the Week 9 loop found. The second line is 0, because the empty list goes straight to the base case. Each call peels off daily[0] and hands daily[1:], a list one item shorter, to the next call, so the list always shrinks toward [].

Worked example — count the calls. To see the calls, put a print at the top of the function and use the first three days.

def total_pages(daily):
    print("call with", daily)
    if daily == []:
        return 0
    return daily[0] + total_pages(daily[1:])

print(total_pages([12, 40, 25]))

Output

call with [12, 40, 25]
call with [40, 25]
call with [25]
call with []
77

Three days made four calls: one for each day and one more for the empty list, where the base case answered. Then the returns added up on the way back: 12 + 40 + 25 = 77.

Misconception check. Students often think daily[1:] removes the first day from daily, so the reading log loses a day on every call. That is tempting, because the list really does get shorter in each new call. But a slice builds a new list and leaves the original alone, as Week 9 showed. The cure: in Python Tutor, look at the first call's frame after the others start; its daily still holds all its days.

In practice (your tools). Paste the count-the-calls program into Python Tutor at pythontutor.com and step through it. Each frame holds a different, shorter list. Then compare the recursive total with the Week 9 loop on the full daily list; both print 154.

Memory hook: peel off the first, hand on the rest, and stop at empty.

8. Spot the missing base case: RecursionError

A song on repeat with no stop button keeps playing until someone pulls the plug. A recursion with no way to stop does the same, and Python is the one that pulls the plug.

RecursionError is the exception Python raises when a chain of recursive calls goes deeper than the interpreter's depth limit, which usually means the base case is missing or never reached.

The depth limit is the cap Python places on how many calls can be open on the call stack at once; it guards against endless recursion, and its number depends on the setup, so it is never memorized.

Worked example — the pinned missing base case. Predict what this prints.

def bad(n):
    return n + bad(n - 1)

print(bad(5))

Output

RecursionError

Nothing printed. bad(5) called bad(4), which called bad(3), and on past 0 into −1, −2, and lower, because nothing told it to stop. Frames piled up until the call stack hit the depth limit, and Python stopped the program. Read the traceback from the bottom up, as in Week 12: the last line names the type, RecursionError. The long middle of the traceback repeats the same line, which is your clue that one call kept calling itself.

Worked example — the same n. This sum_to has a base case, but its recursive call forgets to shrink the input. Predict what it prints.

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n)

print(sum_to(5))

Output

RecursionError

The base case is there, and it is never reached. Every call passes the same 5 to the next call, so n == 0 is never True. The fix is the one character the pinned version has: sum_to(n - 1).

Misconception check. Students often think the recursive call may use the same n, because the base case is "in there somewhere." That is tempting, because the function looks complete. But a base case only helps if each call moves toward it. The cure: look at the recursive call and say how its input is smaller than this call's input; if you cannot, it is not.

Honesty note: a missing base case is the recursion version of the infinite loop from Week 5. A stuck loop runs until you press Stop; a stuck recursion runs until the depth limit, and then Python raises RecursionError for you.

In practice (your tools). Run bad(5) in your browser runner and read the last line of the error. The Standard Library reference's page on the sys module at docs.python.org explains that the limit exists to keep an endless recursion from crashing Python, and that its value differs from setup to setup.

Memory hook: no floor, or no step down, means no stop.

9. Choose recursion when a problem holds smaller copies of itself

Back to the club's shared drive. A folder holds files and more folders, and each of those folders holds files and more folders. Counting the files is "count these, then do the same for each folder inside." When a problem's parts look like smaller copies of the whole, a recursive description often reads more naturally than a loop.

Binary search from Week 13 has the same shape. Each step throws away half of the sorted list and searches the other half, and searching the other half is a smaller copy of the same job.

Worked example — binary search, the recursive way. This version searches between lo and hi and calls itself on one half. It has two base cases: an empty range, which returns -1, and a found target, which returns its index.

def search(items, target, lo, hi):
    if lo > hi:
        return -1
    mid = lo + (hi - lo) // 2
    if items[mid] == target:
        return mid
    elif items[mid] < target:
        return search(items, target, mid + 1, hi)
    else:
        return search(items, target, lo, mid - 1)

pages = [3, 8, 12, 15, 21, 27, 34, 40]
print(search(pages, 21, 0, len(pages) - 1))
print(search(pages, 22, 0, len(pages) - 1))

Output

4
-1

The search finds 21 at index 4, the same index the Week 13 loop version found, and reports -1 for the absent 22. Each recursive call works on a range about half as long, so the range always shrinks toward one of the base cases.

Caveat: the recursive version is not faster than the Week 13 loop. It does the same comparisons; it only describes them differently. A loop is often the plainer choice for a job that walks straight through a list, and recursion is often the plainer choice for folders inside folders.

Worked example — check a chatbot's claim. Suppose you ask a chatbot what countup(3) from Section 5 prints, and it answers: "It counts down from 3 and then prints Go!" Run the program and compare: the run printed Go!, 1, 2, and 3. The chatbot described the countdown it expected, not the code in front of it. In words: one moved line changed the order, and only the run showed it.

Misconception check. Students often think recursion is always better than a loop, or always worse. That is tempting, because people argue about it with strong opinions. But the runs in Section 6 gave the same answers both ways. The cure: pick the version that reads more plainly for the problem in front of you, and run it to confirm the answer.

In practice (your tools). Ask your approved chatbot to write a recursive function that counts the vowels in a word of your choice, and to tell you what it prints. Before you run it, find its base case and its recursive call, and count the vowels yourself. Then run it in your browser runner and compare the three answers: yours, the chatbot's, and the run's.

Caveat: this chapter covers only the recursion Week 14 needs. Functions that call each other in turn, tree structures, and ways of remembering earlier answers come later, in a second course.

Pause and choose one of these to think about before you read on:

  • (a) Think of a task you do that contains a smaller copy of itself, such as cleaning a room that holds a closet that holds boxes. What would the base case be, and what makes each step smaller?
  • (b) Think of a time you followed instructions that never told you when to stop, such as a shampoo bottle's "rinse and repeat." What base case would you add, and where would it go?

Memory hook: trust the run, not the description.

Key terms

  • recursion — A way of solving a problem in which a function calls itself on a smaller copy of the same problem, again and again, until the problem is small enough to answer at once. (first used: 1. Meet a function that calls itself)
  • recursive function — A function whose body contains a call to itself, such as factorial, which hands back n times the factorial of n − 1 for any n above 0. (first used: 1. Meet a function that calls itself)
  • recursive call — A line inside a function that calls that same function, such as the call to countdown with n minus 1 inside countdown; each recursive call opens a new frame of its own. (first used: 1. Meet a function that calls itself)
  • base case — The part of a recursive function that answers without calling the function again, such as returning 1 when n == 0; it is what lets the chain of calls stop. (first used: 2. Give it two parts: the base case and the recursive case)
  • recursive case — The part of a recursive function that calls the function again on a smaller input that moves toward the base case, such as the call to factorial with n minus 1 inside factorial. (first used: 2. Give it two parts: the base case and the recursive case)
  • factorial — The product of every whole number from 1 up to n, so 5 factorial is 5 × 4 × 3 × 2 × 1 = 120; 0 factorial is 1 by definition, which makes it a natural base case. (first used: 3. Build a value on the way back: factorial)
  • call stack — The pile of frames Python keeps for the calls that have started and not yet returned, with the newest call on top; a call adds a frame and a return removes it. (first used: 4. Watch the call stack pile up and unwind)
  • unwinding — The second half of a recursion, when the deepest call returns first and each waiting frame in turn finishes its remaining lines and returns to the call below it on the stack. (first used: 5. Read what runs after the call: unwinding and return values)
  • iteration — Repeating a block of code with a loop such as for or while, as opposed to repeating work by having a function call itself; a problem solved both ways gives the same answer. (first used: 6. Solve it both ways: recursion versus iteration)
  • RecursionError — The exception Python raises when a chain of recursive calls goes deeper than the interpreter's depth limit, which usually means the base case is missing or never reached. (first used: 8. Spot the missing base case: RecursionError)
  • depth limit — The cap Python places on how many calls can be open on the call stack at once; it guards against endless recursion, and its number depends on the setup, so it is never memorized. (first used: 8. Spot the missing base case: RecursionError)

Summary

  • A recursive function calls itself on a smaller input.
  • The base case answers without calling again; the recursive case moves toward it.
  • factorial(5) makes six calls and returns 120.
  • Calls pile up on the call stack and come off in reverse order.
  • Lines after a recursive call run while the stack unwinds.
  • A function that only prints returns None.
  • Recursion and a loop give the same answer.
  • No base case, or no smaller input, means RecursionError.

Check your understanding

Work these before looking at the answers — they are ungraded, and the answers (with reasoning) are at the bottom of the page.

  1. A fitness app in an illustrative example has climb(n), which prints top and returns when n == 0, and otherwise prints step and n and then calls climb(n - 1). Predict every line climb(2) prints.
  2. A math helper in an illustrative example has power(base, exp), which returns 1 when exp == 0 and otherwise returns base * power(base, exp - 1). Predict what print(power(3, 4)) prints, and say how many calls it makes.
  3. A bike-share app in an illustrative example has count_bikes(docks), which returns 0 for the empty list and otherwise returns docks[0] + count_bikes(docks[1:]). Predict what print(count_bikes([4, 0, 7, 2])) prints.
  4. A recipe app in an illustrative example has halve(n), which returns 1 when n == 1 and otherwise returns halve(n // 2). Predict what print(halve(8)) prints, and then predict what print(halve(0)) does.

Answers (worked reasoning — read after attempting)

  1. The run prints step 2, then step 1, then top. The call with 2 prints its line and calls climb(1), which prints its line and calls climb(0), the base case, which prints top. The base case's line comes last, as in the countdown.
  2. The run prints 81, since 3 × 3 × 3 × 3 × 1 = 81. It makes 5 calls, for exp = 4, 3, 2, 1, and 0; the last one is the base case and returns the 1. That is one more call than the 4 multiplications, exactly as factorial(5) made six calls for five numbers.
  3. The run prints 13, since 4 + 0 + 7 + 2 = 13. The calls see [4, 0, 7, 2], [0, 7, 2], [7, 2], [2], and [], five calls in all, and the empty list returns 0.
  4. halve(8) prints 1: the calls go 8, 4, 2, 1, and the call with 1 is the base case. halve(0) never prints. 0 // 2 is 0, so every call passes 0 again and never reaches n == 1; the run stops with RecursionError. A small input can still miss the base case.

Next up in this module: the Readings & Resources page, the lecture tutorial, the practice set, and the quiz — and next week, a class bundles data with each method that works on it, a new rule for organizing a program.

Built with The Course Maker · samples.thecoursemaker.com