City University of Hong Kong · FACULTY OF INFORMATION TECHNOLOGY

IS5312 Chap.6 Recursion, Generators and Comprehensions

- one subject, every graph, every model, every mark
5 Chapters5-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 6 of 6 · IS5312

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.

In this chapter

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

Q [9 marks]. The marks shown are an AskSia study allocation and are not the University marking scheme. Evaluate the recursive sum from zero through four and prove the base case.
The calls do not disappear when the problem shrinks.The calls do not disappear when the problem shrinks. Each frame waits for the smaller result, then combines that result while the stack unwinds.Recursion reduces, reaches a base case, then unwindssum(4)sum(3)sum(2)sum(1)sum(0): baseEach return supplies the result required by the waiting caller.
The calls do not disappear when the problem shrinks. Each frame waits for the smaller result, then combines that result while the stack unwinds.
  • 3State the base case.
  • 3Expand each reducing call.
  • 3Unwind and check the result.
The base returns zero. The call for four expands to four plus the call for three, continuing down to zero. Unwinding returns 1, 3, 6 and 10, matching the direct sum from zero through four. Its score is an AskSia study allocation created for this guide, not an official University scheme.
Sia tip — Test the base, then the first value that uses it, before a normal input.
Glossary

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.
FAQ

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.

Study strategy

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.

A+Everything unlocked
Unlocks this Bible + all 31 of your subjects at City University of Hong Kong, plus 1,000+ more Bibles across the AskSia library.
Sia - your IS5312 tutor, unlimited, worked the way the exam marks it
The full 5-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works