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: