CS: Recursion and Base Cases
Tracing recursive calls and identifying stopping conditions
CS: Recursion and Base Cases
Tracing recursive calls and identifying stopping conditions
CS - Grade 9-12
- 1
A recursive function is a function that calls itself. Explain why every recursive function needs a base case.
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. - 2
Consider this pseudocode: function countdown(n): if n == 0: print("Done") else: print(n) countdown(n - 1). What is the base case?
Look for the condition that stops the recursive call.
The base case is n == 0. When n equals 0, the function prints "Done" and does not call itself again. - 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".
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. - 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)?
Expand the recursive calls before adding the values.
sumTo(4) returns 10 because it computes 4 + 3 + 2 + 1. - 5
For the function sumTo(n), defined as if n == 1 return 1, otherwise return n + sumTo(n - 1), identify the recursive case.
The recursive case is return n + sumTo(n - 1). This case calls the function again with a smaller value of n. - 6
A student writes this function: function repeat(n): print(n) repeat(n). Explain what is wrong with the function.
Check whether the function ever reaches a stopping condition.
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. - 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)?
factorial(5) returns 120 because it computes 5 * 4 * 3 * 2 * 1 * 1. - 8
In the factorial function, why is factorial(0) defined to return 1 instead of 0?
Think about what happens at the final multiplication step.
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. - 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)?
mystery(4) returns 8 because it adds 2 four times before reaching the base case: 2 + 2 + 2 + 2 + 0. - 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?
Think about the smallest possible list.
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. - 11
Consider this pseudocode: function printStars(n): if n == 0: return else: print("*") printStars(n - 1). How many stars are printed by printStars(6)?
printStars(6) prints 6 stars. Each recursive call prints one star, and the function stops when n reaches 0. - 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.
Try evaluating the function for n = 0, n = 1, and n = 2.
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).