CODEWITHSUNDEEP
pythonrecursionfractals
user7091167
user7091167

Reputation:

Infinite loop in recursive program

i'm having an infinite loop in a recursive program that should not be here. My program is made to draw the Sierpinski triangle (http://en.wikipedia.org/wiki/Sierpinski_triangle). Here is my code:

from Python32_Lja import*

init_window("Triangle de Sierpienski",600,600)
current_color(0,0,0)

A=[100,475]#A=[x1,y1]
B=[500,475]#B=[x2,y2]
C=[300,125]#C=[x3,y3]

def Sierpienski(A,B,C,n):

    if n==0:#On trace le triangle

        line(A[0],A[1],B[0],B[1])#AB
        line(B[0],B[1],C[0],C[1])#BC
        line(C[0],C[1],A[0],A[1])#CA

    else:

        MAB=[int((A[0]+B[0])/2),int((A[1]+B[1])/2)]#Milieu de AB
        MBC=[int((B[0]+C[0])/2),int((B[1]+C[1])/2)]#Milieu de BC
        MCA=[int((C[0]+A[0])/2),int((C[1]+A[1])/2)]#Milieu de CA

        line(MAB[0],MAB[1],MBC[0],MBC[1])
        line(MBC[0],MBC[1],MCA[0],MCA[1])
        line(MCA[0],MCA[1],MAB[0],MAB[1])

        A=MAB
        B=MBC
        C=MCA

    return(Sierpienski(A,B,C,n-1))

n=int(input("Entrez le nombre de profondeur : "))        
Sierpienski(A,B,C,n)

main_loop()

It's homework so there is some condition. The algorithm must be recursive, i need to use the Python32_Lja library (simplified Tkinter). I don't know why there is an infinite loop because the function return "n-1" that should end the program.

Upvotes: 0

Views: 250

Answers (2)

xnx
xnx

Reputation: 25508

In your corrected version, you're only drawing the centre triangles. Try drawing each edge of the each triangle at each depth-layer, and the escaping from the recursion when you reach n==0: 

def Sierpienski(A,B,C,n):

    if n==0:#On trace le triangle
        line(A[0],A[1],B[0],B[1])#AB
        line(B[0],B[1],C[0],C[1])#BC
        line(C[0],C[1],A[0],A[1])#CA
        return


    MAB=[int((A[0]+B[0])/2),int((A[1]+B[1])/2)]#Milieu de AB
    MBC=[int((B[0]+C[0])/2),int((B[1]+C[1])/2)]#Milieu de BC
    MCA=[int((C[0]+A[0])/2),int((C[1]+A[1])/2)]#Milieu de CA

    Sierpienski(A, MAB, MCA, n-1)
    Sierpienski(MAB, MBC, B, n-1)
    Sierpienski(C, MBC, MCA, n-1)


    return

Upvotes: 0

Daniel Roseman
Daniel Roseman

Reputation: 599540

You don't have a base condition: you always return a recursive call with n-1, even if n is already 0. You should add a blank return inside the if block, so that it returns and terminates the recursion if n=0.

Alternatively, since the recurrence does not actually return anything, you might consider removing the return statements altogether, and just making the recursive Sierpienski() call inside the else block.

Upvotes: 3

Related Questions