Many early computer games attempted to overcome constraints on memory and storage by generating their game levels using PCG techniques on-the-fly. Elite is one of the first examples of this.
The technique is to use a random seed or a hash of a user supplied string which remains constant, and then grow the playing field iteratively using this number permuted by pseudorandom number generator techniques. Usually growth is from a top-down subdivision, which lends itself well to fractal generation techniques, as well as matching typical level of detail (LOD) implementations. The map is never held in memory except as a temporary structure to display, and is discarded as soon as components of it are no longer required: nothing procedurally generated is ever written back out to disk.
There are several issues to be aware of with this method. The first is that changing the algorithm, changes the world. What this means is that tweaking any parameters or techniques in the procedural content generation method will completely change the generated content. The second is that top down generation can prevent including any content which has a bottom up dependency. A good example of this is a river, which flows from a highest point, to a low point. Since the height of any grid is not known until a certain depth in generation is reached, it is not possible to determine which grids contain a river unless all possible grids are held in memory at the same time. The particular implementation may prevent this.