What two components are required to define a function recursively on a finite set?
Think about your answer, then reveal below.
Model answer: A base case specifying the function's value on the smallest (or minimal) element, and a recursive step specifying how to compute the function's value at any element from its values at smaller elements.
Without the base case, the recursion has no starting point and never terminates. Without the recursive step, there is no rule for computing values beyond the base case. Both are necessary and together they uniquely determine the function.
Question 2 Short Answer
Why does a recursive definition always terminate on a finite set?
Think about your answer, then reveal below.
Model answer: Because a finite set has no infinite descending chains under any strict order. Every sequence of 'smaller' steps must eventually reach the minimal element (base case), guaranteeing termination.
This is the well-foundedness condition applied to finite sets. An infinite set like the integers under < is NOT well-founded (you can always go to a smaller integer), which is why recursive definitions over the integers need extra care. Finite sets avoid this problem entirely.
Question 3 Multiple Choice
Define f(4) recursively, where f(0) = 1 and f(n) = n × f(n−1). What is f(4)?
A4
B10
C24
D16
f(1) = 1×f(0) = 1×1 = 1; f(2) = 2×f(1) = 2×1 = 2; f(3) = 3×f(2) = 3×2 = 6; f(4) = 4×f(3) = 4×6 = 24. This is the factorial function — a classic example of recursive definition on a finite initial segment of the naturals.