Почти там с рекурсией.Одна последняя вещь

Question

Благодаря переполнению стека, я почти закончил с проблемой программирования, которая сводила меня с ума. Это рекурсивно, и вот как это выглядит:

def changeling(word,target,steps):
    x=word
    z=target
    if steps==0:
        return []
    if x==z:
        return [z]
    if len(word)!=len(target):
        print "error"
        return None
    i=1

    if lookup(z[0]+x[1:]) is True and z[0]+x[1:]!=x :
        word=z[0]+x[1:]
    while i!=len(x):
        if lookup(x[:i-1]+z[i-1]+x[i:]) and x[:i-1]+z[i-1]+x[i:]!=x:
            word=x[:i-1]+z[i-1]+x[i:]

        i+=1
    if lookup(x[:len(x)-1]+z[len(word)-1]) and x[:len(x)-1]+z[len(x)-1]!=x :
        word=x[:len(x)-1]+z[len(word)-1]


    return [x]+changeling(word,target,steps-1)

если я введу:

changeling("find","lose"4)

Я получаю:

['find', 'fine', 'line', 'lone', 'lose']

Какой именно вывод я хочу. Мой следующий шаг в программе это. Если слово не может быть изменено на целевое слово за определенное количество шагов, функция просто возвращает None. Так что, если бы я должен был ввести:

подменыша ( "найти", "потерять", 3)

Я ничего не должен получить, но вместо этого я получаю:

['find', 'fine', 'line']

Я не совсем уверен, как это сделать, любая помощь будет оценена.

Answer 1

Вместо немедленного возврата рекурсии, выполните следующие действия:

y =  changeling(word,target,steps-1)
if y :
  return [x] + y
else:
  return None

Проблема с вашей исходной версией заключается в том, что вы возвращаете то, что было вычислено с добавлением следующих шагов. Если вы не можете найти хорошее слово для продолжения цепочки, то ваша программа выдает None, поэтому вы возвращаете оператор, состоящий из списка допустимых шагов + Нет, что эквивалентно только списку допустимых шагов. Здесь все, что мы делаем, это сначала проверяем, можно ли выполнить следующий шаг, если нет, мы возвращаем только None, а если да, то мы возвращаем все.

Answer 2

Вам нужно только изменить окончательный отчет о возврате:

Я не достаточно свободно говорю на python, чтобы дать вам точный код, поэтому вот псевдокод:

subReturnValue = changeling(word, target, steps-1)

if(subReturnValue.length == (steps-1)) then
     return [x] + subReturnValue
else
    return []