Рекурсия со списками

Question

У меня проблемы с программой, программа берет одно слово, и меняя одну букву за раз, преобразует это слово в целевое слово.Хотя имейте в виду, что преобразованное слово должно быть законным словом в соответствии со словарем слов, которые мне дали.

Мне трудно понять, как сделать его рекурсивным.Программа имеет ограничение на количество шагов, которые она должна предпринять.

РЕДАКТИРОВАТЬ: мне не разрешено вносить глобальный список держателей.

Мой код:

def changeling(word,target,steps):
    holderlist=[]
    i=0
    if steps<0 and word!=target:
        return None

    if steps!=-1:
        for items in wordList:
            if len(items)==len(word):
                i=0

                if items!=word:
                    for length in items:

                        if i==1:
                            if items[1]==target[1] and items[0]==word[0] and items[2:]==word[2:]:
                                if items==target:
                                    print "Target Achieved"
                                    holder.list.append(target)
                                holderlist.append(items)
                                changeling(items,target,steps-1)

                        elif i>0 and i<len(word)-1 and i!=1:
                            if items[i]==target[i] and items[0:i]==word[0:i] and items[i+1:]==word[i+1:]:
                                if items==target:
                                    print "Target Achieved"
                                holderlist.append(items)
                                changeling(items,target,steps-1)

                        elif i==0:
                            if items[0]==target[0] and items[1:]==word[1:]:
                                if items==target:
                                    print "Target Achieved"
                                holderlist.append(items)
                                changeling(items,target,steps-1)

                        elif i==len(word)-1:
                            if items[len(word)-1]==target[len(word)-1] and items[0:len(word)-1]==word[0:len(word)-1]:
                                if items==target:
                                    print "Target Achieved"
                                holderlist.append(items)
                                changeling(items,target,steps-1)
                        else:
                            changeling(None,None,steps-1)

                        i+=1

    return holderlist

Моя самая большая проблема в том, что мой список держателей списков хранения обновляется каждый раз, когда я пытаюсь сделать программу рекурсивной.

Я могу решить ее, если введу данные вручную.Вот что я хочу, чтобы программа делала:

changeling("find","lose",4)
gives me:
['fine','fond']
the program should then do:
changeling('fine','lose',3)
gives me:
['line']
changeling('line','lose',2)
gives me:
['lone']
changeling('lone','lose',1)
gives me:
['lose']
Target Achieved

Answer 1

может быть что-то вроде

def distx(w1,w2):
    if len(w1) != len(w2):return 100000
    score=0
    for i in range(len(w1)):
       score += int(w1[i] != w2[i])
    return score


word_list = ["fine","fond","line","lose","lone"]

def changeling(guess,target,steps):
    my_steps = []
    print "Guess:",guess
    if target == guess:return [guess]
    try:word_list.remove(guess)
    except:pass
    my_steps.append(guess)
    if target != guess and steps >= 0:
        this_step = []
        one_step_away = [w for w in word_list if distx(guess,w) == 1]
        for k  in one_step_away:
            print "     %s->"%guess,k
            this_step.append(changeling(k,target,steps-1))
    my_steps.append( this_step )
    return my_steps
tmp = changeling("find","lose",4)
print tmp