# Dragon Curve

# Introduction

The Dragon Curve is a fractal shape that is created by recursive transformation and is named after the mythological dragon. It is a well-known shape in the field of Computer Science and has various applications in areas like computer graphics, data compression, and cryptography.

# Implementation

The Dragon Curve algorithm is implemented in OCaml programming language using the following steps:

- Define two helper functions
`zig`

and`zag`

that take two points as input and return a new point that lies halfway between them but is rotated 90 degrees. - Define a recursive function
`dragon`

that takes four arguments: two initial points, one point in between them rotated 90 degrees, and an integer`n`

that represents the number of iterations. - If
`n`

is 0, the function returns the two initial points; otherwise, it recursively calls itself with the 4 points and`n-1`

and then concatenates the two resulting lists. - Finally, create a canvas and draw a line connecting the list of points generated by the
`dragon`

function.

# Step-by-step Explanation

- Define two points
`p1`

and`p2`

. - Generate a list of points using the
`dragon`

function with`p1`

,`zig(p1,p2)`

,`p2`

, and`15`

as arguments. This creates a list of points that generate the dragon curve when connected. - Create a canvas with width 430 and height 300.
- Draw a line connecting all the points generated by the
`dragon`

function using the`Canvas.create_line`

function. - Open the main loop of the program using
`Tk.mainLoop ()`

.

# Complexity Analysis

The algorithm has a time complexity of `O(2^n)`

and a space complexity of `O(2^n)`

. This is because at each recursive step, the function creates two new points that generate a line segment, leading to an exponential growth in the number of points generated at each iteration. This can cause performance issues for larger values of `n`

. However, the space complexity can be reduced by eliminating the creation of intermediate lists, which can be achieved by using tail recursion.