Lesson 5

Recursion

Theory

Fractal is a geometric composition which is hard to describe using geometric shapes.

Its characteristic is it repeats itself but with each iteration in smaller scale.

Practice

To create a tree, cloud, landscape, circulatory system, often a model is generated based on parameters chosen by an artist.

Ready model is used in a game/movie.

Hints
  • Recursion is most often used.
  • Effect is an interesting graphic element.

I. Recursion tasks


Task 0

Analyze an example usage of a recursion:

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) {
        
        // Summing two numbers
        System.out.println(sum(6, 9));
        
        // Iteration without a loop
        times(10);
    
    }
}
Task 1

Write a program which calculates a sum of elements in an array (using recursion).

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

II. Drawing a tree


The code below draws one, left branch of a tree.
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);
        // Starting point
        int xFrom = 512;
        int yFrom = 768;
        // Length of a brunch
        int radius = 100;
        // Starting angle
        double angle = Math.PI;

        // Drawing
        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);
    }
}
Task 1

Add drawing a right brunch to a program.

Task 2

Use recursion so draw method will call itself.

Its purpose is to draw a tree with a number of levels given as an argument.

Effect should be similar to the one below.

Fractal tree in swing
Task 3

Modify a code which creates a tree, so it draws a bonsai tree. To do this:

  • Set different thickness for brunches
  • Set different length of brunches in each level
  • Modify values for further angles, lengths with a pseudorandom number.
  • Add coloring
  • Change background
  • (optional) If you want to create an animation you can delay adding brunches by using Thread.sleep.
Task 4 (not mandatory)

Create a program which draws Sierpinski triangle.