CS: Recursion and Base Cases Worksheet

Question 1

A recursive function is a function that calls itself. Explain why every recursive function needs a base case.

Accepted Answer

Every recursive function needs a base case so the function has a condition where it stops calling itself. Without a base case, the function may continue forever until the program crashes or runs out of memory.

Question 2

Consider this pseudocode: function countdown(n): if n == 0: print("Done") else: print(n) countdown(n - 1). What is the base case?

Accepted Answer

The base case is n == 0. When n equals 0, the function prints "Done" and does not call itself again.

Question 3

Trace the output of this function call: countdown(3), where countdown(n) prints n and calls countdown(n - 1) until n == 0, then prints "Done".

Accepted Answer

The output is 3, 2, 1, Done. The function starts at 3 and subtracts 1 each time until it reaches the base case n == 0.

Question 4

Consider this pseudocode: function sumTo(n): if n == 1: return 1 else: return n + sumTo(n - 1). What value is returned by sumTo(4)?

Accepted Answer

sumTo(4) returns 10 because it computes 4 + 3 + 2 + 1.

Question 5

For the function sumTo(n), defined as if n == 1 return 1, otherwise return n + sumTo(n - 1), identify the recursive case.

Accepted Answer

The recursive case is return n + sumTo(n - 1). This case calls the function again with a smaller value of n.

Question 6

A student writes this function: function repeat(n): print(n) repeat(n). Explain what is wrong with the function.

Accepted Answer

The function has no base case and does not change the value of n. It will keep calling itself with the same input and will not stop on its own.

Question 7

Consider this pseudocode: function factorial(n): if n == 0: return 1 else: return n * factorial(n - 1). What value is returned by factorial(5)?

Accepted Answer

factorial(5) returns 120 because it computes 5 * 4 * 3 * 2 * 1 * 1.

Question 8

In the factorial function, why is factorial(0) defined to return 1 instead of 0?

Accepted Answer

factorial(0) returns 1 because it is the base case that allows multiplication to finish correctly. If it returned 0, every factorial result would become 0 when multiplied by the base case.

Question 9

Consider this pseudocode: function mystery(n): if n <= 0: return 0 else: return 2 + mystery(n - 1). What value is returned by mystery(4)?

Accepted Answer

mystery(4) returns 8 because it adds 2 four times before reaching the base case: 2 + 2 + 2 + 2 + 0.

Question 10

A recursive function processes a list by looking at the first item, then calling itself on the rest of the list. What would be a reasonable base case for this function?

Accepted Answer

A reasonable base case is when the list is empty. At that point, there are no more items to process, so the function can stop or return a final value.

Question 11

Consider this pseudocode: function printStars(n): if n == 0: return else: print("*") printStars(n - 1). How many stars are printed by printStars(6)?

Accepted Answer

printStars(6) prints 6 stars. Each recursive call prints one star, and the function stops when n reaches 0.

Question 12

Rewrite this recursive idea in words: function powerOfTwo(n): if n == 0: return 1 else: return 2 * powerOfTwo(n - 1). Include the base case and recursive case in your explanation.

Accepted Answer

The function calculates 2 raised to the power n. The base case is n == 0, which returns 1. The recursive case multiplies 2 by the result of powerOfTwo(n - 1).

CS: Recursion and Base Cases

Related Cheat Sheets

More CS Worksheets

More Grade 9-12 Worksheets