Practice understanding recursion, base cases, recursive cases, and how recursive functions stop.
Read each problem carefully. Trace the recursive calls when needed. Show your work in the space provided.
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.
- 2
Consider this pseudocode: function countdown(n): if n == 0: print("Done") else: print(n) countdown(n - 1). What is the base case?
- 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".
- 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)?
- 5
For the function sumTo(n), defined as if n == 1 return 1, otherwise return n + sumTo(n - 1), identify the recursive case.
- 6
A student writes this function: function repeat(n): print(n) repeat(n). Explain what is wrong with the function.
- 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)?
- 8
In the factorial function, why is factorial(0) defined to return 1 instead of 0?
- 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)?
- 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?
- 11
Consider this pseudocode: function printStars(n): if n == 0: return else: print("*") printStars(n - 1). How many stars are printed by printStars(6)?
- 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.