Lekcja 6

Rekurencja

Teoria

Fraktal to twór geometryczny, który trudno opisać używając kształtów geometrycznych.

Ma taką cechę, że powtarza sam siebie, ale w coraz mniejszej skali.

Praktyka

Aby stworzyć drzewo, chmury, krajobraz, układ krążenia, często generuje się model w oparciu o wybrane przez artystę parametry.

Gotowy model trafia do gry, filmu.

Rady
  • Najczęściej wystarczy wykorzystać rekurencję.
  • Uzyskane efekty są ciekawym elementem graficznym.

I. Ćwiczenia z rekurancji


Zadanie 0

Przeanalizuj przykładowe użycie rekurencji:

class Recursion {

    static int sum(int a, int b) {
        if (b == 0) return a;
        return sum(++a, --b);
    }

    static void times(int i) {
        if (i == 0) return;
        System.out.println("i: " + i);
        times(--i);
    }

    public static void main(String[] args) {
        
        // Dodawanie dwóch liczb
        System.out.println(sum(6, 9));
        
        // Iteracja bez pętli
        times(10);
    
    }
}
Zadanie 1

Napisz program, który wyliczy sumę elementów w jednowymiarowej tablicy (koniecznie z rekurencją).

Podpowiedź: int array_sum(int[ ] tab, int i) { }.

II. Rysowanie drzewa


Poniższy kod rysuje jedną, lewą gałązkę drzewa.
import javax.swing.*;
import java.awt.*;

public class Main {

    public static void main(String[] args) {
        SwingUtilities.invokeLater(() -> {
            new TreeFrame();
        });
    }
}

class TreeFrame extends JFrame {

    public TreeFrame() {
        setSize(new Dimension(1024, 768));
        setVisible(true);
        setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
    }

    public void paint(Graphics g) {
        super.paint(g);
        // Punkt startowy
        int xFrom = 512;
        int yFrom = 768;
        // Długość gałęzi
        int radius = 100;
        // Początkowy kąt
        double angle = Math.PI;

        // Rysowanie
        draw(g, xFrom, yFrom, radius, angle);
    }

    private void draw(Graphics g, int xFrom, int yFrom, double radius, double angle) {

        double deltaAngle = 0.25;

        double leftEndX = xFrom + Math.sin(angle + deltaAngle)*radius;
        double leftEndY = yFrom + Math.cos(angle + deltaAngle)*radius;

        g.setColor(Color.BLACK);
        g.drawLine(xFrom, yFrom, (int)leftEndX, (int)leftEndY);
    }
}
Zadanie 1

Niech program zacznie rysować prawą gałązkę.

Zadanie 2

Spraw, używając rekurencji, aby metoda draw zaczęła wywoływać się rekurencyjnie.

Jej zadaniem jest narysować drzewo o zadanej ilości poziomów gałęzi.

Efekt powinien być zbliżony do tego poniżej.

Drzewo fraktalne rysowane w swingu
Zadanie 3

Zmodyfikuj kod tworzonego drzewa, aby program rysował drzewko bonsai. W tym celu:

  • Nadawaj liniom różne grubości
  • Zmieniaj długości gałązek kolejnych poziomów
  • Modyfikuj wartości kolejnych kątów, długości, o wartość pseudolosową.
  • Dodaj kolorowanie
  • Zmień tło
  • (opcjonalnie) Jeśli chcesz utworzyć animację, możesz opóźniać dodawanie kolejnych gałęzi przez Thread.sleep.
Zadanie 4 (Ciekawostka)

Niech program, który rysuje trójkąt Sierpińskiego.