Ch 06 - Recursion

Supanit Angsirikul

Iteration

void setup() {

for (int i = 1; i <= 10; i++)

println(i);

}

Head Recursive

void head(int n) {

print(n + ",");

if (n < 10)

head(++n);

}

void setup() {

head(1);

}

Tail Recursive

void tail(int n) {

if (n < 10)

tail(n+1);

print(n + ",");

}

void setup() {

tail(1);

}

Iteration

• Iterations do not create new environment in each loop.

​

void itr() {

int x = 0;

for(int i = 0; i < 10; i++)

print(x++ + ",");

}

void setup() {

itr();

}

Recursion

• Recursions create new environment in each invocation.

​

void rec(int i) {

int x = 0;

if (i < 10) {

print(x++ + ",");

rec(++i);

}

}

void setup() {

rec(1);

}

Factorial

/* n! = fac(n) = n * (n-1) * (n-2) .... * 1 */

int facI(int n) { // Iteration

int r = 1;

for(int i = 1; i <= n; i++)

r *= i;

return r;

}

​

/* n! = 1 if n <= 1

= n * (n-1)! Otherwise */

int facR(int n) { // Recursion

if (n <= 1)

return 1;

return n * facR(n-1);

}

​

void setup() {

for(int n = 1; n <= 10; n++)

println(n + ": " + facI(n) + "\t" + facR(n));

}

​

Buying time with memory.

• /*Find abc a three digits integer, such that
• abc = a! + b! + c! */

​

int fac[] = new int[10];

void setup() {

fac[0] = 1; fac[1] = 1;

for(int i = 2; i < fac.length; i++)

fac[i] = i*fac[i-1];

abc();

}

void abc(){

for (int a = 1; a < 10; a++)

for (int b = 0; b < 10; b++)

for (int c = 0; c < 10; c++)

if (100*a + 10*b + c == fac[a] + fac[b] + fac[c])

println(a+""+b+""+c);

}

145

Exponential

• /* Exponential
• expo(a, n) = a * a * ... * a (n times) */

​

• // Iterative Exponential

​

int expo(int a, int n){

int r = 1;

for(int i = 0; i < n; i++)

r *= a;

return r;

}

void setup() {

for (int i = 1; i <= 10; i++)

println(expo(2, i));

}

Recursive Exponential

• /* Recursive Exponential
• expo(a, n) = 1 if n == 0
• = a * expo(a, n-1) otherwise */

​

int expo(int a, int n){

if (n == 0)

return 1;

return a * expo(a, n-1);

}

void setup() {

for (int i = 1; i <= 10; i++)

println(expo(2, i));

}

Divide and Conquer Exponential

• /* Divide and Conquer Exponential
• expo(a, n) = 1 if n == 0
• = expo(a*a, n/2) if n is even
• = a * expo(a*a, n/2) if n is odd */

​

int expo(int a, int n){

if (n == 0)

return 1;

if (n % 2 == 0)

return expo(a*a, n/2);

return a * expo(a*a, n/2);

}

void setup() {

for (int i = 1; i <= 10; i++)

println(expo(2, i));

}

Fibonacci

• /* Fibonacci
• fib(n) = 1 ถ้า n <= 2 : fib(0)=1 , fib(1)=1, fib(2)=2
• = fib(n-1)+ fib(n-2) */

​

// Recursive Fibonacci

int fib(int n){

if (n <= 2)

return 1;

return fib(n-1) + fib(n-2);

}

void setup() {

for (int i = 1; i <= 10; i++)

print(fib(i) + ",");

// println(fib(45));

}

Iterative Fibonacci

int fib(int n){

int a, b, c, i;

a = b = c = 1;

i = 3;

while (i++ <= n) {

c = a + b;

a = b;

b = c;

}

return c;

}

void setup() {

for (int i = 1; i <= 10; i++)

print(fib(i) + ",");

// println(fib(45));

}

*** Faster than Recursive

Iterative Draw

​

size(300, 200);

for(float x = 0; x < width; x++)

line(x, 20, x, 180);

Recursive Draw

​

void drawLine(float x) {

line(x, 20, x, 180);

if (x < width)

drawLine(++x);

}

void setup() {

size(300, 200);

drawLine(0);

}

Active Mode Draw

void setup() {

size(300, 200);

}

int x = 0;

void draw() {

line(x, 20, x, 180);

if (x++ > width)

noLoop();

}

​

Recursive Circles

void circle(int x, int y, int s) {

if (s > 3) {

ellipse(x, y, s, s);

circle(x-s/2, y, s/2);

// circle(x+s/2, y, s/2);

// circle(x, y-s/2, s/2);

// circle(x, y+s/2, s/2);

}

}

void setup() {

size(300, 300);

background(255);

smooth();

noFill();

translate(width/2, height/2);

circle(0, 0, width/2);

}

Two Color Circles

void circle(int x, int y, int r, int n) {

ellipse(x, height/2, r*2, r*2);

ellipse(width/2, y, r*2, r*2);

if (--n > 0) {

fill(random(255), random(255), random(255), 125);

circle(x - r/2, y, r/2, n);

// circle(x + r/2, y, r/2, n);

// circle(x, y - r/2, r/2, n);

// circle(x, y + r/2, r/2, n);

}

}

void setup() {

size(600, 600);

noStroke();

smooth();

circle(width/2, height/2, height/2, 9);

}

​

Recursive Circles

void drawCircle(int x, int y, int s) {

if (s > int(random(2, 10))) {

ellipse(x, y, s, s);

if(random(3) > 1) drawCircle(x-s/2, y, s/2);

if(random(3) > 1) drawCircle(x+s/2, y, s/2);

if(random(3) > 1) drawCircle(x, y-s/2, s/2);

if(random(3) > 1) drawCircle(x, y+s/2, s/2);

}

}

void display() {

background(255);

pushMatrix();

translate(width/2, height/2);

drawCircle(0, 0, int(random(width/3, width/2)));

popMatrix();

}

void setup() {

size(800, 800);

smooth();

noFill();

frameRate(0.5);

}

void draw() {

display();

}

boolean stop;

void mousePressed() {

if (stop)

loop();

else

noLoop();

stop = !stop;

println(stop);

}

​

Deep Sky

• Circles are given random positions relative to the previous position. At each level of recursion, the size of the circles decrease, their distance from the previous level decreases, and their colors grow darker.

​

​

void setup() {

size(800, 600);

noStroke();

circle(width/2, height/2, width/2, 10);

}

void draw() {

}

void mousePressed() {

background(255);

circle(width/2, height/2, width/2, int(random(5, 15)));

}

​

void circle(float x, float y, int r, int n) {

fill(random(255-n), random(255-n), random(255-n), 125);

ellipse(x, y, r*2, r*2);

if (--n > 1) {

int m = int(random(2, 6));

for (int i = 0; i < m; i++) {

float a = random(0, TWO_PI);

float nx = x + cos(a) * 6.0 * n;

float ny = y + sin(a) * 6.0 * n;

circle(nx, ny, r/2, n);

}

}

}

Deep Sky

Recursive Squares

float min = 20; // try: 5

void box(float cx, float cy, float d) {

if (d > min) {

strokeWeight(0.1*d);

stroke(d, 0, 0); // stroke(d);

rect(cx, cy, d, d);

box(cx-d/2, cy-d/2, d/2);

box(cx+d/2, cy-d/2, d/2);

box(cx-d/2, cy+d/2, d/2);

box(cx+d/2, cy+d/2, d/2);

}

}

void setup() {

size(400, 400);

rectMode(CENTER);

noFill();

stroke(0);

noLoop();

}

void draw() {

background(255);

box(width/2, height/2, width/2);

println(min);

}

​

void mouseMoved() {

if (mouseY < pmouseY)

--min;

else

++min;

redraw();

}

Draw T

void drawT(int x, int y, int a, int n) {

line(x, y, x, y-a);

line(x-a, y-a, x+a, y-a);

if (n > 0) {

drawT(x-a, y-a, a/2, n-1);

drawT(x+a, y-a, a/2, n-1);

}

}

void setup() {

size(400, 300);

noLoop();

int x = width/2;

int y = height;

int a = width/4;

int n = 5;

drawT(x, y, a, n);

}

Tree 1

void tree(float x0, float y0, float len, float a) {

if (len > 2) {

float x1 = x0 + cos(radians(a))*len;

float y1 = y0 - sin(radians(a))*len;

stroke(len, 200-len, len);

line(x0, y0, x1, y1);

tree(x1, y1, len*0.75, a + 30);

tree(x1, y1, len*0.66, a - 50);

}

}

void setup() {

size(800, 800);

background(255);

tree(width/2, height, 175, 90);

}

Tree 2

void tree(float len, float a) {

if (len > 2) {

rotate(radians(a));

line(0, 0, len, 0);

translate(len, 0);

pushMatrix();

// tree(len*0.75, -30);

// tree(len*0.75, -10);

tree(len*0.80, -10);

popMatrix();

pushMatrix();

tree(len*0.66, 50);

popMatrix();

}

}

void setup() {

size(800, 800);

background(255);

translate(width/2, height);

tree(175, -90);

}

Tree 3

float a1 = 0.75, a2 = 0.66;

float r1 = -10, r2 = 50;

​

void tree(float len, float a) {

if (len > 2) {

rotate(radians(a));

line(0, 0, len, 0);

translate(len, 0);

pushMatrix();

tree(len*a1, r1);

popMatrix();

pushMatrix();

tree(len*a2, r2);

popMatrix();

}

}

void display() {

background(160);

pushMatrix();

translate(width/2, height);

tree(width/4, -90);

popMatrix();

textSize(25);

text(a1+","+r1, 20, 30);

text(a2+","+r2, 20, 60);

}

​

​

void setup() {

size(800, 800);

display();

}

void draw() {

}

void keyPressed() {

if (key == 'a')

a1 -= 0.01;

else if (key == 's')

r1 -= 3;

if (key == 'q')

a1 += 0.01;

else if (key == 'w')

r1 += 3;

if (key == 'd')

a2 -= 0.01;

else if (key == 'f')

r2 -= 3;

else if (key == 'e')

a2 += 0.01;

else if (key == 'r')

r2 += 3;

display();

}

ลองกดปุ่ม a / s / q / w / d / f / e / r

Assignment #5

• Write a program using recursion to draw the image as shown.