Trying to understand the Levy Curve (fractal)

Question

I am asked to implement a recursive function that takes a nonnegative integer n as input and returns turtle instruction encoded with letters L,R and F where L means rotate left 45 degrees, R means rotate right 45 degress and F means go forward.

Additional information i have i: for every nonnegative integer n>0, the Levy curve L(n) can be defined in terms of Levy curve L(n-1); Levy curve L(0) is just a straight line.

    usage:
    >>> lev(0)
    'F'
    >>> lev(1)
    'LFRRFL'

I am very new to this and I am not sure how to start:

so far I only got:

    from turtle import Screen, Turtle
    def lev(n):
        # base case
        if n ==0:
           return 'F'
        # recursive case
        else:
            return lev(n-1)

I need some good pointers here please.

Answer 1

Since Levy C's L system only has a single rule, it's simple to build the resulting string using a single replace method.

def lev(n):
    if n == 0:
        return "F"
    else:
        symbols = lev(n-1)
        return symbols.replace("F", "LFRRFL")

for i in range(4):
    print lev(i)

Result:

F
LFRRFL
LLFRRFLRRLFRRFLL
LLLFRRFLRRLFRRFLLRRLLFRRFLRRLFRRFLLL

You can visualize this replacement by imagining each straight line in the figure being replaced by two smaller lines connected at a ninety degree angle. Like so:

Answer 2

First, in case this is the problem: A large Levy curve (recursive case) is constructed by arranging two smaller ones facing each other 'across the room', with two more 'on the floor' facing up, in between. A small Levy curve (base case) is just a straight line. So indeed, the base case is:

def lev(n):
    if n == 0:
        return 'F'
    else:
        # Recursive case here

But for the recursive case, you just have it call lev(n-1). You are right that you will need to do this, but you will need to do it four times, and rotate in between. This will create the desired 'two smaller curves facing each other, with two in between'.

Inspecting the curve carefully (here: https://en.wikipedia.org/wiki/File:Levy_C_construction.png), we see that we will need to draw one curve, then turn right, then draw another, then turn completely around, then draw a third curve, and finally, turn right and draw the final curve.

This can be done fairly simply:

dev lev(n):
    if n == 0:
        # Base case
        return 'F'
    else:
        # Recursive case
        # Calculate the smaller curve
        smaller = lev(n-1)
        # Add in the turning in between the smaller curves
        final = smaller        # First curve
        if n%2 == 0:           # Even depths require right turns
            final += 'RR'        # Rotate 90 degrees
            final += smaller     # Second curve
            final += 'RRRR'      # Rotate 180 degrees
            final += smaller     # Third curve
            final += 'RR'        # Rotate 90 degrees
            final += smaller     # Final curve
        else:                  # Odd depths require left turns
            final += 'LL'        # Rotate 90 degrees
            final += smaller     # Second curve
                                 # (No full rotation in odd depths)
            final += smaller     # Third curve
            final += 'LL'        # Rotate 90 degrees
            final += smaller     # Final curve
        return final           # Done!

Answer 3

My Answer

import turtle

def draw(n):
    l=10
    if n == 0:
        turtle.forward(l)
    else:
         turtle.left(45)
         draw(n - 1)
         turtle.right(45)
         turtle.right(45)
         draw(n-1)
         turtle.left(45)

draw(12)