Mar 122018Like all important ideas, recursion can be thought about in many ways, and there is no single “correct” or “best” way to think about it.
Rather, each way of thinking is useful for some purposes, but not helpful in every situation.
In the posts about recursion on trees and linked lists, we thought about:
- What recursion is,
- How to find recursive structures in problems, and
- How to write simple recursive functions to solve those problems.
We haven’t yet thought about how recursive functions actually work — what happens when a recursive function is called?
In this post we’ll see three different ways to think about how recursive functions are actually computed.
Mar 122018A linked list is a recursive structure — a linked list node has a value, and a pointer to the next linked list node.
This means we can solve problems on linked lists using structural recursion.
In this post we’ll see three examples, to demonstrate the process of writing a structurally recursive algorithm.
Mar 122018Recursion is one of the most difficult ideas in programming, but sometimes it can be simple.
A recursive function is a function which can call itself.
Some recursive functions are very puzzling, but others are so natural that you can understand them even without knowing what recursion is.
Mar 052018Before attempting these exercises, you should read the posts about graphs, graph problems, and graph data structures.
Mar 052018A graph is an abstract model of a relation between pairs of things.
In the previous post we identified many relations which can be modelled as graphs; however, we don’t yet have any data structures to represent graphs in computer programs.
Mar 052018Graphs and networks are useful because they’re very general — graphs show up almost everywhere.
Given that there are so many different examples of graph structures, then, it’s perhaps surprising that there aren’t actually very many different kinds of problems involving graphs.
That is, there are many computing problems which graphs can help with, but not many kinds of problem.
Usually, after translating from the problem domain into the language of graphs, the problem turns out to be one of a relatively small number of “classical graph problems”.
Mar 052018A tree is an abstract idea, a common kind of structure which we find across many different applications.
A tree models a relation between pairs of things:
- A section of an article contains another section,
- A directory contains another directory,
- An HTML tag contains other HTML tags,
- An employee manages another employee,
- A process spawns another process.
A “relation between pairs of things” is very abstract and very general — in almost any context, there are relations between pairs of things which we might want to model in a computer program.
However, not every relation defines a tree structure.
Feb 262018Before attempting these exercises, you should read the posts about trees, ways to think about trees, and tree data structures.
Feb 262018Before attempting these exercises, you should read the posts about trees and ways to think about trees.
Feb 262018Abstract data types define what data can be represented and what operations can be performed on it, but not how the data should be stored or structured in a program.
Data structures are concrete implementations of ADTs which fill in these details — they define how the data should be stored in memory, and what instructions should be followed to perform the operations.
Trees are both; we have an abstract idea of what a tree is, but there are also data structures for them, which we’ll look at in this post.
In fact, we can even use tree data structures to implement other ADTs, such as sets or dictionaries.(1)
