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:

  1. 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.
  2. 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.
  3. 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.
  4. Finally, create a canvas and draw a line connecting the list of points generated by the dragon function.

Step-by-step Explanation

  1. Define two points p1 and p2.
  2. 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.
  3. Create a canvas with width 430 and height 300.
  4. Draw a line connecting all the points generated by the dragon function using the Canvas.create_line function.
  5. 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.