Recursion: a function calling itself

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. Which function is recursive?

A def countdown(n): ... countdown(n - 1)

B def countdown(n): ... print(n)

2. What is the job of the base case in a recursive function?

A It stops the recursion by returning without calling the function again

B It makes the function call itself one more time

3. Which line is the base case of a factorial function?

A if n == 0: return 1

B return n * factorial(n - 1)

4. Which line is the recursive case in a countdown function?

A if n == 0: return

B countdown(n - 1)

5. What does Python raise if a recursive function has no base case?

A SyntaxError

B RecursionError

Match the Pairs

Draw a line connecting each item on the left to its match on the right.

Left column		Right column
1if n == 0: return 1		Adef forever(n): return forever(n - 1)
2return n * factorial(n - 1)		Bdef countdown(n): if n == 0: return countdown(n - 1)
3A countdown function stops at its base case and otherwise calls itself with a smaller number		CThe recursive call makes the problem bigger (n + 1), so n never reaches the base case. It should be countdown(n - 1).
4A function with no base case never stops calling itself, so Python raises a RecursionError		DThere is no base case, so the function never stops and raises a RecursionError. Add if n == 0: return 1 first.
5def factorial(n): return n * factorial(n - 1)		EThe base case: it returns a value without calling the function again, so the recursion stops
6def countdown(n): if n == 0: return countdown(n + 1)		FThe recursive case: the function calls itself with a smaller problem (n - 1)

Definitions

recursion

Fill in the Blanks

Complete each line of code by filling in the missing parts.

def factorial(n): if n == 0: ______ 1

def fact(n): if n <= 1: return 1 return n * ____(n - 1)

def total(n): if n == 0: return 0 return n + total(n _ 1)

def forever(n): return forever(n + 1) # Raises ______________

def countdown(n): __ n == 0: return countdown(n - 1)

Spot the Error

Shade in the letter of the line that contains an error.

Question 1

A def count_down(n):

B if n = 0:

C return

D print(n)

E count_down(n - 1)

Question 2

A def factorial(n)

B if n <= 1:

C return 1

D return n * factorial(n - 1)

Question 3

A def blast_off():

B if n == 0:

C print("Blast off!")

D return

E print(n)

F blast_off(n - 1)

Question 4

A def total(n):

B if n == 1:

C return 0

D return n + total(n - 1)

Question 5

A def say_hi(n):

B if n == 10:

C return

D print("Hi")

E say_hi(n - 1)

Answer Key

Recursion: a function calling itself

Section A: Quick Questions

A — def countdown(n): ... countdown(n - 1)

A — It stops the recursion by returning without calling the function again

A — if n == 0: return 1

B — countdown(n - 1)

B — RecursionError

Section B: Match the Pairs

if n == 0: return 1 → The base case: it returns a value without calling the function again, so the recursion stops

return n * factorial(n - 1) → The recursive case: the function calls itself with a smaller problem (n - 1)

A countdown function stops at its base case and otherwise calls itself with a smaller number → def countdown(n): if n == 0: return countdown(n - 1)

A function with no base case never stops calling itself, so Python raises a RecursionError → def forever(n): return forever(n - 1)

def factorial(n): return n * factorial(n - 1) → There is no base case, so the function never stops and raises a RecursionError. Add if n == 0: return 1 first.

def countdown(n): if n == 0: return countdown(n + 1) → The recursive call makes the problem bigger (n + 1), so n never reaches the base case. It should be countdown(n - 1).

Section C: Definitions

recursion — A function that calls itself with a smaller problem each time, and stops at a base case that returns without calling itself. With no base case, Python raises a RecursionError.

Section D: Fill in the Blanks

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

def fact(n):
    if n <= 1: return 1
    return n * fact(n - 1)

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

def forever(n):
    return forever(n + 1)
# Raises RecursionError

def countdown(n):
    if n == 0: return
    countdown(n - 1)

Section E: Spot the Error

B — A single = assigns a value, so it cannot be used in a condition. The base case check must use == to compare: if n == 0:

A — A function header must end with a colon. It should be def factorial(n):

A — The function needs the parameter n. The body uses n and the recursive call passes n - 1, so the header should be def blast_off(n):

B — The base case should be n == 0 so that total(0) returns 0. Stopping at 1 returns 0 for 1, so total(3) gives 5 instead of 6.

B — n counts down from a small number such as 3, so it never equals 10. The base case is never reached and Python raises a RecursionError. It should be if n == 0: