Start learning →

Recursion and data structures

Thinking recursively, avoiding repeated work, and building the classic structures that the rest of computer science is made of.

About 9 hours of study

Learning objectives

Lessons

  1. 1

    Recursion in practice Intermediate

    Recursive sums, fast powers and the Tower of Hanoi, with every call visible on the stack.

  2. 2

    Memoization Intermediate

    Remember answers you have already computed, and turn slow recursion into fast recursion.

  3. 3

    Stacks and queues Intermediate

    Last in, first out and first in, first out: two ways to line up work, and where each is used.

  4. 4

    Linked lists Intermediate

    Chain objects together with references, walk the chain, insert in the middle, and reverse it.

  5. 5

    Binary trees Intermediate

    Build trees of nodes with left and right children, and solve tree problems with recursion.

Module practice

Module quiz

1. Why is memoization so effective for Fibonacci?
2. Which structure suits a printer's waiting jobs?
3. What goes wrong if you write current.next = prev before saving current.next?
4. Inserting 1, 2, 3, 4, 5 in order into a search tree gives what shape?
5. What is the base case for a function on a tree?
6. Why use deque rather than list.pop(0) for a queue?

‹ Objects and classesAlgorithms and projects ›