How does a recursion that produces recurring appointment dates from a start date differ from one that consumes a list?
answer
- direction of travel
- argument shrinks, or output grows
- seed and step, not base case
- termination proof versus productivity
- one element handed back per step
basics
~20 sA consuming recursion takes an existing value apart and shrinks toward a base case; a producing one grows a result outward from a seed. A decreasing measure is replaced by handing back one piece per step.
solid answer
~40 sBoth call themselves, but opposite things drive them. A consuming recursion is driven by its argument: it splits the list of dates, calls itself on the shorter rest, and stops at the empty case, so correctness follows from a measure that strictly decreases. A producing recursion is driven by a `step`: given a **seed** — the start date plus the repeat rule's state — it hands back one date and the seed for the rest, and the result is built outward. The seed need never get smaller, so there may be no base case to reach; the argument for correctness becomes **productivity**, meaning every step delivers a date before it recurses. Consuming asks *will this finish?*; producing asks *will the next piece always arrive?*
code
pseudocode · 8 lines// consuming: the argument shrinks toward the empty case
function countDates(dates)
if dates is empty then return 0
return 1 + countDates(rest of dates)
// producing: nothing shrinks; a seed describes what is left to build
function datesFrom(seed)
return prepend(seed.date, datesFrom(advance(seed)))go deeper
Recall that recursion has two directions: one takes a value apart until nothing is left, the other builds a value up from a starting point. Be able to say which direction a date generator is working in.
Explain what stands in for the base case. A producer is judged on delivering one element per step rather than on reaching a smallest argument, and you should be able to name the seed and the step as separate pieces.
Show it in review. Point at a producer whose step can take a path that emits nothing, and say why that path, rather than a missing base case, is the failure worth flagging in a date generator.
Treat it as an interface decision. Publishing a seed and a step lets every caller decide how far to go; publishing a finished list of dates forces you to pick a horizon once, on behalf of callers you have not met.
## Two directions, one word Recursion is usually taught in one direction only. A function receives a value, takes it apart, calls itself on a strictly smaller piece, and stops at a smallest case that cannot be taken apart any further. Correctness rests on a **measure** — the length of the remaining list, the depth of a subtree, a counter — that decreases on every call, plus a **base case** waiting at the bottom. That is consumption: the input drives the recursion, and the result is usually smaller than what went in. Corecursion runs the other way. Nothing is taken apart. The function receives a **seed**: a small value describing where the production has got to. For a recurring appointment that is the anchor date, the repeat interval, and how many occurrences have already been handed out. The function's job is to hand back **one element and the next seed**. The result grows outward, and the seed need never get smaller: from *every second Tuesday, starting on this date* there is no smallest seed and no bottom to reach. ## What replaces the base case A consuming recursion is justified by an argument that it **finishes**. A producing one is justified by an argument that it **keeps delivering**. Each turn of the definition must hand back a piece of the result before it recurses — that property is called **productivity**, and it is not the same property as termination: - Termination asks: does the chain of calls reach a case that contains no call? - Productivity asks: does each further piece of the result become available after finitely many steps? - A definition can be productive and never end. An endless appointment series is exactly that, and it is not a defect. - A definition can look like it is making progress and still fail productivity: a step that changes the seed but emits nothing has advanced and produced nothing. The review consequence is concrete. On a consuming recursion you hunt for the missing or unreachable base case. On a producing one you hunt for a path through the step that recurses without handing anything back. ## The appointment series, concretely Consuming the dates looks like this: given a list of past appointments, count them, or find the latest. Each call peels one date off the front and calls itself on the rest; after `n` calls the rest is empty and the base case answers. The recursion is finished by the data. Producing them looks like this: given the anchor date and the rule, hand back the anchor, then produce the rest from an advanced seed. There is no list to peel. The only thing that makes this a definition rather than a riddle is that the anchor is handed back **before** the call that produces the rest. A producer may also stop — a rule that says *ten occurrences* carries the remaining count in its seed and reports *no more* when it reaches zero — but it does not need to stop in order to be well defined. ## Side by side | | consuming recursion | producing (corecursive) recursion | |---|---|---| | driven by | the shape of the argument | the step function applied to a seed | | needs | a decreasing measure and a base case | one element handed back per step | | seed or input | an already-built structure | a small description of what is left to build | | result | usually smaller than the input | usually larger than the seed | | ends when | the argument is exhausted | the step reports stop, or the caller asks for no more | | classic failure | the base case is never reached | a step path that emits nothing | ## Where the two directions meet They are directions of reasoning, not two disjoint species of function: 1. A step that reads the next entry from an existing calendar and reshapes it consumes on its input side and produces on its output side. Both arguments apply, to different halves. 2. A bounded producer carries its bound inside the seed, so it ends without ever being driven by an input structure. It is still corecursive; the stop is the step's decision, not the data's. 3. The vocabulary mirrors as well: the operation that collapses a structure into one value and the operation that grows a structure from a seed are reflections of each other, which is why the second is usually named as the first one reversed. ## What an interviewer is listening for A weak answer treats every recursion as consumption and calls a missing base case a bug on sight. A solid answer names the direction first, then names what each direction has to prove — a measure that decreases on one side, an element delivered per step on the other — and can point at the line in a producer where the element is handed back. That single line is the whole difference.
- Can one function be both consuming and producing?Yes. A step that reads the next entry from an existing calendar and reshapes it consumes on its input side and produces on its output side, and a producer bounded to ten occurrences consumes a countdown it carries in its own seed. The two words describe the direction you argue correctness in, not two disjoint kinds of function.
- If the seed never shrinks, what stops the producer from running forever?Nothing inside the definition, and nothing needs to. A producer is judged on whether each step delivers a piece, not on whether the whole run ends. A particular run ends when the step itself reports that there are no further elements, or when whoever is reading stops asking for more.
A consuming recursion is a stack of dishes you work down until the sink is empty. A producing one is a calendar printer that can always run off the next page, for as long as anyone keeps asking for pages.
saying these in an interview costs you the question
- Says any recursion without a base case is a bug
- Thinks a producer must shrink something to be correct
- Calls the seed the input list and looks for its end
- Assumes a producing recursion can never stop
- Claims the only difference is lazy versus eager evaluation