Co-recursion
In functional programming, corecursion is all about creating the steps by using the output of one step as the input of next step, starting with the first step. It works synthetically, starting from base case. It is a bottom up approach which generates data from a base case. It is used to produce arbitrarily complex and infinite structures such as streams in a sequence of finite steps. Its often used with lazy evaluation just to generate a finite part of a potentially infinite structure.
Recursion
Recursion is slightly the same as corecursion. The only difference lies in its approach. It breaks down problem in simpler steps until the simplest or most fundamental steps are reached(base case). It works analytically, starting from the data and repeating itself until it reaches the base case, more of a top-down approach which reduces tasks as it calls itself.
Parts of Recursion.
- Base Case : This is the condition which terminates the recursive method. It is the most fundamental step which can be solved without the use of any more recursive calls. If this condition is met, then the recursive method starts to unwind and returns some value with each method being unwound.
- Recursive Step: Generally formed by principle of mathematical induction, it defines a given problem in terms of smaller problem. It involves invoking the same function but with a reduced set of input.
- Return Value : This is the combination of the several outputs produced by subroutines. It basically involves aggregation or calculation of some data based on the results of the recursive calls.
Syntax of Recursion.
This is the basic syntax for any recursive method.
<access-specifier> <modifier> <return-type> methodName(formal-arguments-list) {
if(base condition)
return something..
return methodName(simpler-formal-arguments-list);
}Nth Fibonacci Number:
public int fibonacciSeries(int n) {
if(n <= 1)
return 1;
return fibonacciSeries(n-1) + fibonacciSeries(n-2);
}Problem Statement: Fractal Trees.
Fractal trees are a kind of pattern exhibiting self similarity which means that they repeat the same shape or pattern at different scales. There are several algorithms that can help you generate fractal trees but as usual, the simplest out of all is the recursive approach.
Recursion minimizes the effort of defining more and more variables and avoids making a spaghetti code.
Fractal trees have many applications in real world technology. They can be used to model several real life objects in games such as coral reefs and create visually astonishing patterns and designs.
What do you need to proceed further?
There are a few requirements to continue further with this post. It includes a basic knowledge of Graphics Development in Java. Since this post intends to provide a clear visual insight of Fractal trees, it goes on to depict a fractal tree in a graphics environment and hence having a slight idea of graphics programming would be handy.
Starting off..
Let’s understand and begin writing an algorithm for creating a Fractal tree.
Algorithm
- Define a method drawFractalTree(int, int, int, int) that takes the starting coordinates (x,y) of a branch, the angle between the branches angle with respect to the vertical, and the height of the fractal tree height.
- Base Case: We should understand that if a user specifies the height of the tree as 0, then we must not proceed to draw another branch. And hence this becomes the base case of our program. It will be here that our recursive calls ends.
- Compute the next coordinates of the fractal tree branch with the help of predefined Math functions, given the angle in radians.
x-coord = cos(angleRad) * height * depth
y-coord = sin(angleRad) * height * depth
4. This is the sole way to generate the other two coordinates of the fractal branch. Given two x coordinates and two y-coordinates, we can connect the two points using the drawLine(int, int, int, int) function of Graphics class.
5. Now we invoke the drawFractalTree method again but with some modified angle and reduced height.
Program.
Every explanation of a programming problem is nothing without the pseudo code. Here’s how you’ll implement the drawFractalTree method.
void drawFractalTree( x, y, angle, height) :
if height == 0
return
x2 = cos( toRadians(angle) ) * height * depth
y2 = sin( toRadians(angle) ) * height * depth
drawLine(x, y, x2, y2)
drawFractalTree(x2, y2, angle - 10, height - 1)Rest of the Program.
- Creating the Driver class : This will start the Application by invoking the run method in Application class.
package com.projectjava;
public class Main {
public static void main(String[] args) {
Application.run(args);
}
}2. Creating the Application class : This class is responsible to create and display the fractal tree.
package com.projectjava;
import java.swing.JFrame;
public class Application extends JFrame {
...
}3. Adding the run method to Application class : The method sets the size, title and the visibility of the frame created.
public static void run(String[] args) {
var app = new Application();
app.setSize(700, 700);
app.setVisible(true);
app.setTitle("Fractal Trees");
}4. Add a default constructor to the class : Without this, your program won’t terminate even if you close your application as it would keep running in the background.
public Application() {
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
this.setResizable(false);
}5. Add the paint(Graphics) method to the Application class and invoke the recursive method that draws the fractal tree branches : The paint() method is responsible to draw the graphical components on a JPanel or JFrame window. With the use of Graphics class, you can draw lines, shapes, text and images on the window. We invoke the recursive method drawFractalTree() and initiate the recursive method with some default coordinates and angles.
@Override
public void paint(Graphics g) {
drawFractalTree(250, 650, -90, 10);
}6. Lastly, add the recursive method drawFractalTree(): This recursive method invokes itself with different angles and values and draws the branches of the fractal trees.
public void drawFractalTree(int x, int y, int angle, int height, Graphics g) {
if (height == 0)
return;
int x2 = (int)Math.cos(Math.toRadians(angle)) * height * 10;
int y2 = (int)Math.sin(Math.toRadians(angle)) * height * 10;
g.setColor(Color.WHITE);
g.drawLine(x, y, x2, y2);
drawFractalTree(x2, y2, angle-20, height-1);
drawFractalTree(x2, y2, angle+20, height-1);
}If you like to have cherries on your fractal trees after so much of understanding, its quite easy. You just need to manipulate the base case a bit and add some more things to it.
if(height == 0) {
g.setColor(Color.RED);
g.fillOval(x-2, y, 5, 5);
} Output
Is this all that you need? Yes, you’re done with the programming part. But wait, this isnt over yet. Let’s now understand the functioning of this in this youtube video.
That’s all for this post, thanks for giving it a read. I hope you understood the applications of Recursion. Thanks!!
