A rather simple one (that is given as an exercise in recursion in many LOGO classes) is to draw the Koch Snowflake.
A slightly more complex one would be the Mandelbrot set. The basic concept behind it is this:
You have a set of numbers, called Complex numbers. The basic concept is that they define $i=\sqrt{-1}$. Yep, it's a number which doesn't exist, but it's extremely useful. A Complex number is any "number" of the form $a+bi$. These don't exist either (unless $b=0$), so another way to look at a complex number is that it is a point on the coordinate plane, $(a,b)$. Just like you can plot numbers on a number line, complex numbers can be plotted on the Cartesian plane. They multiply and divide normally, just pretend that $i$ is any run-of-the-mill variable and replace all $i^2$s with $-1$ when they appear.
So how does this relate to a fractal? Well, let's consider this recursive relation for a given complex number $c$:
$z_{i+1}=z_{i}^2+c,z_0=0$
Basically, this means you take the number $c$, add it to $z_0^2=0$, and get $z_1$. You plug $z_1$ back into the equation (square it and add $c$), and you get $z_2$. And so on.
Now, you check if this sequence of $z$s escapes to infinity (i.e., the $a$ or $b$ becomes infinite). If it doesn't do so within some fixed number of iterations, the number belongs in this "Mandelbrot set".
Now, all you do is take some fixed area of the coordinate plane (The most common is to let x range from $-2$ to $1$, and y from $-1$ to $1$), and check which points in the area belong to the set (By this, I mean "check if the complex number $x+iy$ corresponding to the point $(x,y)$ is in this set"). Plot the point if it belongs to the set, and you get a beautiful snowman-like thing.
It gets even more interesting if you replace the $z^2$ with some other power (note that fractional powers will require you to know a bit more about complex numbers)