Бесконечный цикл в рекурсивной программе

у меня бесконечный цикл в рекурсивной программе, которого здесь быть не должно. Моя программа предназначена для рисования треугольника Серпинского (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). Я не знаю, почему существует бесконечный цикл, потому что функция возвращает «n-1», что должно завершить программу.


python recursion fractals
person Community    schedule 04.01.2015    source источник
comment
Вы его отладили? Как в попытке выяснить, почему это неправильно. Вы, вероятно, заметите, что бесконечный цикл имеет смысл, если вы это сделаете.   -  person keyser    schedule 04.01.2015

Ответы (2)


arrow_upward
0
arrow_downward

В вашей исправленной версии вы рисуете только центральные треугольники. Попробуйте нарисовать каждое ребро каждого треугольника на каждом уровне глубины и выйти из рекурсии, когда вы достигнете 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
person xnx    schedule 04.01.2015
comment
Спасибо за вашу помощь! - person ; 05.01.2015
comment
У меня только что возникла мысль: ваш рисунок линии действительно должен быть только на самой низкой глубине - см. Мое редактирование. - person xnx; 05.01.2015

arrow_upward
3
arrow_downward

У вас нет базового условия: вы всегда возвращаете рекурсивный вызов с n-1, даже если n уже равно 0. Вы должны добавить пробел return внутри блока if, чтобы он возвращал и завершает рекурсию, если n=0.

В качестве альтернативы, поскольку повторение на самом деле ничего не возвращает, вы можете рассмотреть возможность полного удаления операторов return и просто сделать рекурсивный вызов Sierpienski() внутри блока else.

person Daniel Roseman    schedule 04.01.2015
comment
Спасибо, сэр, но теперь он не рисует то, что должен рисовать. - person ; 04.01.2015
comment
Что ж, @Paul, это не очень полезный комментарий. Я предлагаю вам сначала попробовать разобраться и, если это не сработает, вернуться с подробным вопросом. Я полагаю, что на ваш первоначальный вопрос был дан ответ: рекурсивная функция всегда должна сталкиваться с завершающим условием. - person Roy Prins; 05.01.2015