The term Fractal was coined and popularized by Benoit B Mandelbrot. It describes a broad set of shapes. Defining characteristics include non-integer dimension, or an interesting mismatch of dimension (Hausdorff dimension strictly exceeding topological dimension), and detail at all scales or self-similarity. Fractals are frequently used in procedural content generation because self-similarity seems to mimic natural processes such as erosion and plant growth. The subdivision method also maps well onto level of detail implementations: allowing an 'infinite' amount of detail to be included by recursively subdividing the detail shown as the view point moves closer to the fractal object.
Perlin noise is a fractal algorithm.
A simple fractal that can be generated at any dimension takes an initial point, subdivides it by n, then randomly chooses n ^ d points. This is recursively repeated for all points selected.
Examples with dimensions 0.5, 1.0, 1.5:
For source see fractal_simple.py
PCG Wiki References
The following images on Flickr are generated using fractals: