IS5312 Chap.6 Recursion, Generators and Comprehensions
Recursion, Generators and Comprehensions
This chapter extends function design with recursion, lambda expressions, generators and comprehensions. A recursive solution must contain a direct base case and a reducing step that reaches it for every permitted input. Yield creates a lazy generator that preserves state between values. List, set and dictionary comprehensions create collections, while parenthesised comprehension syntax creates a generator.
Compact syntax is expanded into loops whenever its state is unclear.
What this chapter covers
- 01
Lambda expressions and f-strings
- 02
Recursive base and reducing cases
- 03
Call-stack unwinding
- 04
Yield and lazy generators
- 05
List, set and dictionary comprehensions
Worked example · free
Unwind a recursive sum
- 3State the base case.
- 3Expand each reducing call.
- 3Unwind and check the result.
Key terms
- Base Case
- A recursive input answered without another recursive call.
- Reducing Step
- The transformation that makes a recursive problem smaller.
- Generator
- An iterable that produces values lazily while preserving execution state.
Recursion, Generators and Comprehensions FAQ
What makes recursion terminate?
Every permitted input must move through the reducing step toward a base case with a direct answer. Test the base input, one reduction and a normal input to verify both termination and unwinding.
How is yield different from return?
Return ends the call with one object, while yield pauses the function and can resume to produce later values. The caller can therefore consume values on demand without first storing an entire result collection.
Why is a tuple comprehension a generator?
Parenthesised comprehension syntax evaluates lazily and does not construct a tuple unless explicitly converted. Convert it explicitly only when a finished tuple is actually required by the surrounding program.
Assessment move
Treat advanced syntax as a compression of behaviour you can already trace. For recursion, write the base case in words and test it before the reducing step. Then state how every permitted input becomes smaller and why the sequence of calls must reach the base. Expand a small call such as a sum for four into separate lines, leave space for each waiting result, and unwind from the base upward.
Compare the final value with a direct calculation. Repeat with a palindrome so the reduction removes matching outside characters and the base handles length zero or one. Add invalid inputs and decide whether the contract rejects them or defines another base case. For generators, write the state that survives between yields.
Request one value at a time and record where execution pauses, then consume the rest and test what happens after exhaustion. Compare that behaviour with returning a complete list. Use a finite divisible-number sequence and a short Fibonacci sequence so expected outputs are available by hand.
For lambda practice, rewrite a one-expression regular function as a lambda and explain why a multi-step validation should remain a named function. For comprehensions, read in a fixed order: output expression, source collection, filter. Expand each into a normal loop before running it. Build one list transformation, one set that intentionally removes duplicates and one dictionary mapping source items to derived values.
Parenthesise the same expression and confirm that it creates a generator rather than a tuple. Keep an evaluation table with columns for result type, eager or lazy, preserves order, removes duplicates and can be consumed more than once. Finish with an integrated comparison: solve one filtering problem with an ordinary loop, a list comprehension and a generator expression.
Verify identical produced values, then explain the memory and timing differences without claiming that the shortest form is always clearest. In timed work, choose recursion only when the problem is naturally self-similar and the reduction is obvious. Choose a generator when values should arrive on demand. Choose a comprehension when one transformation and at most one clear filter fit on a readable line.
Expand anything whose state cannot be explained immediately. Add a termination proof to every recursive exercise. Name a nonnegative measure of problem size, show that each call reduces it and identify the value handled directly by the base case. Then trace the return path separately from the call path so waiting operations are not lost.
For generators, compare two objects created by separate calls with one object consumed twice; the first pair begins from fresh state, while the exhausted object does not restart. Record when input conversion or calculation happens to make lazy timing observable. For comprehensions, prepare one source in which a filter rejects a value whose transformed form would pass a different test.
This reveals whether filtering is applied to the source or output. End by solving one finite task four ways: an ordinary loop, list comprehension, set comprehension and generator expression. State the result type, ordering, duplicate behaviour and consumption model for each.
Select the form from the required contract rather than from brevity, and retain the expanded loop as an oracle until every produced value and edge case agrees.