Session 10: Recursion, Iteration & Data Structures I

Overview

Recursion and iteration as two presentations of the same computation, what each costs in memory, and how to state and prove an invariant.

Lecturer

Georges Khater (CSE + Mathematics)

Session Information

• Date and Time: Thursday 22 October 2026 — 17:30-19:30
• Place: (to be announced)
• Online Meeting Link
• Session Recording

Core Concepts

• Recursive vs iterative formulations of the same algorithm, and translating between them
• The call stack: stack frames, what recursion costs, and stack overflow
• Tail recursion and accumulator passing
• Memory model: the stack vs the heap, references, and pointers
• Arrays vs linked lists
• Stacks and queues: interface, implementation, and applications
• Invariants: what one is, how to state it, and how to prove it is maintained
• Loop invariants: initialization, maintenance, and termination

Slides

Session 10 Slides: Download PDF

Readings

• CLRS, Ch. 2, 10

Exercises & Extra Steps

• Practice (not collected): convert a recursive sum to tail-recursive form and prove the two agree by induction
• Practice (not collected): state and prove the loop invariant for insertion sort
• Practice (not collected): for a queue built from two stacks, state the invariant relating them and prove the amortized cost is O(1)

Navigation

• ← Previous: S9: Induction II — Structural and Well-Founded Induction
• Back to Course Overview
• Next: S11: Data Structures II — Trees, Heaps, Graphs →

Questions? Reach out on the course WhatsApp!