Functions Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
Consolidate your functions mastery by exploring recursion, modular problem solving, and function composition.
Recursion: a function calling itself
Recursion is when a function solves a problem by calling itself on a smaller version of that problem. It needs a base case to stop.
A recursive function solves a problem by breaking it into smaller instances of the same problem. Every recursive function must have a base case to stop recursion.
def factorial(n): if n <= 1: return 1 return n * factorial(n - 1)
print(factorial(5))Example 1 · Power by repetition
def power(base, exp): if exp == 0: return 1 return base * power(base, exp - 1)
print(power(2, 5))32
What this code does
- Calculates 2⁵ recursively.
- Returns 32 once the base case
exp == 0is reached.
Example 2 · Count down with recursion
def countdown(n): if n == 0: print("Go!") return print(n) countdown(n - 1)
countdown(3)3 2 1 Go!
What this code does
- The base case is
n == 0: it printsGo!and stops. - Every other call prints
nand callscountdownwith a smaller number.
The base case n <= 1 stops the call stack from growing. For n=5, it computes 5 * 4 * 3 * 2 * 1 = 120.
Euclidean GCD algorithm
Euclidean algorithm finds the greatest common divisor of two numbers by replacing (a, b) with (b, a % b) until b is 0. The answer is then a.
The greatest common divisor (GCD) of two numbers can be found efficiently using the Euclidean algorithm: $GCD(a, b) = GCD(b, a \% b)$.
def gcd(a, b): return a if b == 0 else gcd(b, a % b)
print(gcd(48, 18))Example 3 · Following gcd step by step
def gcd(a, b): print(f"gcd({a}, {b})") if b == 0: return a return gcd(b, a % b)
print(gcd(84, 36))gcd(84, 36) gcd(36, 12) gcd(12, 0) 12
What this code does
- Each call prints its arguments: (84, 36), then (36, 12), then (12, 0).
- When b is 0 the base case returns a, and that 12 travels back out as the final answer.
The algorithm computes gcd(48, 18) -> gcd(18, 12) -> gcd(12, 6) -> gcd(6, 0) = 6 in logarithmic O(log min(a, b)) time.
Finish up
Mark complete & continue
Next: Must-do problems: Functions