递归程序中的无限循环

Question

我在递归程序中遇到了一个不应该出现在这里的无限循环。我的程序是用来绘制 Sierpinski 三角形 (http://en.wikipedia.org/wiki/Sierpinski_triangle) 的。这是我的代码：

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()

这是家庭作业，所以有一些条件。该算法必须是递归的，我需要使用 Python32_Lja 库（简化的 Tkinter）。我不知道为什么会出现无限循环，因为函数 return "n-1" 应该结束程序。

Answer 1

你没有一个基本条件：你总是 return一个n-1的递归调用，即使n已经是0。你应该添加一个if 块内的空白 return，以便它 returns 并在 n=0 时终止递归。

或者，由于递归实际上 return 没有任何作用，您可以考虑完全删除 return 语句，并只在 else 块内进行递归 Sierpienski() 调用。

Answer 2

在您更正后的版本中，您只绘制了中心三角形。尝试在每个深度层绘制每个三角形的每条边，并在到达 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

递归程序中的无限循环

Infinite loop in recursive program

python

recursion

fractals