Delphi: Sierpinski triangle: procedure not running itself completely

Question

I don't understand why this code draws this:

Only the bottom-left triangles seem to draw, however the inner-triangles appear only in the first depth of the top- and bottom-right triangle. I want the procedure to be recursive, but it is somehow cause of my shitty programming skills not recursive. I really want an understanding of what I am doing wrong.

implementation

{$R *.dfm}

var
  count : integer = 0;

procedure DrawTriangle(aCanvas: TCanvas;x,y,size : extended;n : integer);
var
  h : extended;
  w : extended;
  i : integer;
  x1,x2,x3,y1,y2,y3 : extended;
begin
    w := size;
    h := size;
    x1 := x;
    y1 := y;
    //ShowMessage(FloatToStr(w)+' '+FloatToStr(h));
  if aCanvas<>nil then
  try
    //1st - left
    aCanvas.MoveTo(Round(x1),Round(y1));
    aCanvas.LineTo(Round(x1+w*2),Round(y1));
    aCanvas.LineTo(Round(x1+w),Round(y1-h));
    aCanvas.LineTo(Round(x1),Round(y1));
    //2nd - right
    x2 := x1+w*2;
    y2 := y1;
    aCanvas.MoveTo(Round(x2),Round(y2));
    aCanvas.LineTo(Round(x2+w*2),Round(y2));
    aCanvas.LineTo(Round(x2+w),Round(y2-h));
    aCanvas.LineTo(Round(x2),Round(y2));
    //3rd - top
    x3 := x2-w;
    y3 := y2-h;
    aCanvas.MoveTo(Round(x3),Round(y3));
    aCanvas.LineTo(Round(x3+w*2),Round(y3));
    aCanvas.LineTo(Round(x3+w),Round(y3-h));
    aCanvas.LineTo(Round(x3),Round(y3));

    //Run itself
    inc(count);
    if count < n then
    begin
      DrawTriangle(aCanvas,x1,y1,size/2,n);
      DrawTriangle(aCanvas,x2,y2,size/2,n);
      DrawTriangle(aCanvas,x3,y3,size/2,n);
    end;
  except
    on e: exception do raise e;
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  size : extended;
  i : integer;
  x,y : extended;
begin
  size := 100;
  x := 100;
  y := 400;
  DrawTriangle(Image1.Canvas,x,y,size,10);
end;
end.

Answer 1

The problem is that you draw the first triangle, then you call DrawTriangle to draw the bottom-left part, which does that, and then calls DrawTriangle to draw the new bottom-left part, and so on, until count has reached n. Then we return one procedure at a time to the original procedure, and in each step we draw the remaining two triangles only once.

The following logic works as intended. (Remove the global count variable.)

procedure DrawTriangle(aCanvas: TCanvas; x, y, size: extended; n: integer);
var
  h: extended;
  w: extended;
  x1, x2, x3, y1, y2, y3: extended;
begin
  w := size;
  h := size;
  x1 := x;
  y1 := y;

  //1st - left
  aCanvas.MoveTo(Round(x1), Round(y1));
  aCanvas.LineTo(Round(x1+w*2), Round(y1));
  aCanvas.LineTo(Round(x1+w), Round(y1-h));
  aCanvas.LineTo(Round(x1), Round(y1));
  //2nd - right
  x2 := x1+w*2;
  y2 := y1;
  aCanvas.MoveTo(Round(x2), Round(y2));
  aCanvas.LineTo(Round(x2+w*2), Round(y2));
  aCanvas.LineTo(Round(x2+w), Round(y2-h));
  aCanvas.LineTo(Round(x2), Round(y2));
  //3rd - top
  x3 := x2-w;
  y3 := y2-h;
  aCanvas.MoveTo(Round(x3), Round(y3));
  aCanvas.LineTo(Round(x3+w*2), Round(y3));
  aCanvas.LineTo(Round(x3+w), Round(y3-h));
  aCanvas.LineTo(Round(x3), Round(y3));

  //Run itself
  if n > 0 then
  begin
    DrawTriangle(aCanvas, x1, y1, size/2, n-1);
    DrawTriangle(aCanvas, x2, y2, size/2, n-1);
    DrawTriangle(aCanvas, x3, y3, size/2, n-1);
  end;
end;

I leave it as an exercise to figure out why it works.

Also notice I removed the completely unnecessary try..except block.

Finally, you can write the code much more efficiently, as demonstrated by Sir Rufo.

Answer 2

Your attempt to limit the depth of recursion contains an error.

You draw each of the 3 inner triangles and increment count, and then call DrawTriangle again to draw the triangles within those triangles. Each call increments count again, meaning that count does not reflect the depth of recursion but simply how many times DrawTriangle has been called. As a result of specifying a limit of 10, you will find that in your results, 10 sets of triangles have been drawn.

Instead of incrementing count to track recursion depth you should decrement n for each call until n = 0.

To make this intention clearer you can use a nested procedure where the outer call accepts the maximum number of levels of recursion specified with the inner, nested procedure doing the actual recursion indicating the number of levels remaining and decrementing this number for the recursive calls themselves:

procedure DrawTriangle(aCanvas: TCanvas;x,y,size : extended; maxLevels: integer);

  procedure Draw(x,y,size: extended; levelsLeft: integer);
  var
    h : extended;
    w : extended;
    i : integer;
    x1,x2,x3,y1,y2,y3 : extended;
  begin
    w := size;
    h := size;
    x1 := x;
    y1 := y;

    //1st - left
    aCanvas.MoveTo(Round(x1),Round(y1));
    aCanvas.LineTo(Round(x1+w*2),Round(y1));
    aCanvas.LineTo(Round(x1+w),Round(y1-h));
    aCanvas.LineTo(Round(x1),Round(y1));

    //2nd - right
    x2 := x1+w*2;
    y2 := y1;
    aCanvas.MoveTo(Round(x2),Round(y2));
    aCanvas.LineTo(Round(x2+w*2),Round(y2));
    aCanvas.LineTo(Round(x2+w),Round(y2-h));
    aCanvas.LineTo(Round(x2),Round(y2));

    //3rd - top
    x3 := x2-w;
    y3 := y2-h;
    aCanvas.MoveTo(Round(x3),Round(y3));
    aCanvas.LineTo(Round(x3+w*2),Round(y3));
    aCanvas.LineTo(Round(x3+w),Round(y3-h));
    aCanvas.LineTo(Round(x3),Round(y3));

    //Run itself
    if (levelsLeft > 0) then
    begin
      Draw(x1, y1, size/2, levelsLeft - 1);
      Draw(x2, y2, size/2, levelsLeft - 1);
      Draw(x3, y3, size/2, levelsLeft - 1);
    end;
  end;

begin
  if Assigned(aCanvas) then
    Draw(x, y, size, maxLevels);
end;

This also allows pre-conditions to be tested in a clearer fashion, in this case limited currently to ensuring that a canvas has been specified, but could also involve normalising or validating other parameters as might be required, before initiating the recursive call.

Since the original parameters remain in scope for the nested procedure it also means that you can limit the parameters in the calls to the recursive procedure to only those which actually change on each call. (I have updated the code in my answer to incorporate this).

Incidentally, a try..except that simply raises any caught exceptions is exactly equivalent to having no try..except block at all so I removed it from this implementation.

Also you might wish to consider adding an additional condition to halt recursion if the value of size reaches a certain minima (where the inner triangles are indistinct, e.g. size < 2).

Answer 3

Just as an addition to the given answers, here is a DRY version:

procedure DrawTriangleDRY( aCanvas: TCanvas; CenterX, CenterY, Width, Height: extended; n: integer );
begin
  aCanvas.MoveTo( Round( CenterX ), Round( CenterY - Height / 2 ) ); // top
  aCanvas.LineTo( Round( CenterX + Width / 2 ), Round( CenterY + Height / 2 ) ); // bottom right
  aCanvas.LineTo( Round( CenterX - Width / 2 ), Round( CenterY + Height / 2 ) ); // bottom left
  aCanvas.LineTo( Round( CenterX ), Round( CenterY - Height / 2 ) ); // top

  // draw childs
  if n > 0
  then
    begin
      // top
      DrawTriangleDRY( aCanvas, CenterX, CenterY - Height / 4, Width / 2, Height / 2, n - 1 );
      // left
      DrawTriangleDRY( aCanvas, CenterX - Width / 4, CenterY + Height / 4, Width / 2, Height / 2, n - 1 );
      // right
      DrawTriangleDRY( aCanvas, CenterX + Width / 4, CenterY + Height / 4, Width / 2, Height / 2, n - 1 );
    end;
end;

---

Update

I just realized, that this can be optimized to only draw the last childs

procedure DrawTriangleDRY( aCanvas: TCanvas; CenterX, CenterY, Width, Height: extended; n: integer );
begin
  // draw childs
  if n > 0
  then
    begin
      DrawTriangleDRY( aCanvas, CenterX, CenterY - Height / 4, Width / 2, Height / 2, n - 1 ); // top
      DrawTriangleDRY( aCanvas, CenterX - Width / 4, CenterY + Height / 4, Width / 2, Height / 2, n - 1 ); // left
      DrawTriangleDRY( aCanvas, CenterX + Width / 4, CenterY + Height / 4, Width / 2, Height / 2, n - 1 ); // right
    end
  else
    begin
      aCanvas.MoveTo( Round( CenterX ), Round( CenterY - Height / 2 ) ); // top
      aCanvas.LineTo( Round( CenterX + Width / 2 ), Round( CenterY + Height / 2 ) ); // bottom right
      aCanvas.LineTo( Round( CenterX - Width / 2 ), Round( CenterY + Height / 2 ) ); // bottom left
      aCanvas.LineTo( Round( CenterX ), Round( CenterY - Height / 2 ) ); // top
    end
end;