Функция Collatz не завершается правильно

Вот программа, которая предназначена для рекурсивного подсчета длины последовательности Коллатца:

def odd_collatz ( n ):
    return (3 * n) + 1

def even_collatz ( n ):
    return int(n / 2)

def collatz_counter ( initialNumber, initialLength ):
    length = initialLength

    while True:
        if initialNumber == 1:
            return length

        elif initialNumber != 1:
            length += 1

            if initialNumber % 2 == 0:
                 collatz_counter(even_collatz(initialNumber), length)

            else:
                collatz_counter(odd_collatz(initialNumber), length)

print(collatz_counter(13, 1)

Ожидаемый ответ - 10. Однако программа застревает в бесконечном цикле. На предпоследнем шаге последовательности initalNumber равно 2. Программа работает должным образом: collatz_counter вызывается с использованием even_collatz и числа 10.

Ожидаемым действием следующего шага будет запуск collatz_counter с initialNumber, равным 1, и initialLength, равным 10. Я ожидал, что произойдет то, что первый оператор if будет иметь значение true, collatz_counter должен вернуть length, а затем выйти. Однако это не то, что происходит:

На самом деле происходит то, что функция оценивает первый оператор if, запускает строку return length, а затем переходит к строке кода под if initialNumber % 2..., и весь процесс повторяется снова и снова в бесконечном цикле.

Есть идеи относительно того, почему это может происходить?


python function recursion collatz
person superstewie    schedule 20.08.2016    source источник
comment
Если начальное число не 1, предложения elif и else ничего не возвращают. Вы также вызываете функцию внутри себя: collatz_counter   -  person Andrew    schedule 20.08.2016
comment
Исправьте код. Похоже, в последних нескольких строках collatz_counter() отсутствует закрывающая скобка. Кроме того, как предполагает @Andrew, эти строки должны быть return collatz_counter(...)   -  person Warren Weckesser    schedule 20.08.2016
comment
Я его отредактировал. Это были опечатки только в SE, в реальном коде они были правильными. linusG предупредил меня, и я их исправил. Эндрю, поэтому я не могу понять, в чем проблема, это оценка того, что не следует оценивать.   -  person superstewie    schedule 20.08.2016
comment
А теперь еще одна опечатка: должно быть print(collatz_counter(13, 1)), вы пропустили одну закрывающую скобку.   -  person linusg    schedule 20.08.2016

Ответы (3)


arrow_upward
3
arrow_downward

Вы смешиваете рекурсию и цикл несколько странным образом. Проблема в while True:. Поскольку вы никогда ничего не возвращаете из цикла, ничто не мешает этому продолжаться вечно. Ваш код достигает 1, а затем просто продолжает увеличивать длину. Вот исправленная версия.

def odd_collatz ( n ):
    return (3 * n) + 1

def even_collatz ( n ):
    return int(n / 2)

def collatz_counter ( initialNumber, initialLength ):
    length = initialLength


    if initialNumber == 1:
        return length

    elif initialNumber != 1:
        length += 1

        if initialNumber % 2 == 0:
            return collatz_counter(even_collatz(initialNumber), length)

        else:
            return collatz_counter(odd_collatz(initialNumber), length)

print(collatz_counter(13, 1))
person qfwfq    schedule 20.08.2016
comment
Это решило это! И я кое-что узнал о том, как правильно делать рекурсию. Спасибо - person superstewie; 20.08.2016

arrow_upward
2
arrow_downward

Мне кажется, это опечатка. Вы определяете функцию collatz_counter, ожидающую двух чисел.

Но вы называете это так:

...
print(collatz_counter(13), 1)

Просто попробуйте изменить последнюю строку на:

print(collatz_counter(13, 1))

И все должно быть хорошо.

Надеюсь это поможет!

person linusg    schedule 20.08.2016
comment
Чтобы избавиться от этого, если length по умолчанию равен 0, он увеличивается до 1 до того, как функция перейдет в саму себя, и функция вернется, потому что теперь длина равна 1. - person dckuehn; 20.08.2016
comment
Это была опечатка, когда я напечатал это здесь. В программе все правильно написано. Спасибо за внимание! Я поменял его в ОП - person superstewie; 20.08.2016

arrow_upward
0
arrow_downward

Основная ошибка - это зацикливание while True: вкупе с отсутствием возвратов.

def odd_collatz ( n ):
    return (3 * n) + 1

def even_collatz ( n ):
    return int(n / 2)

def collatz_counter(initialNumber, length):
    if initialNumber == 1:
        return length
    elif initialNumber != 1:
        length += 1
        if initialNumber % 2 == 0:
             return collatz_counter(even_collatz(initialNumber), length)
        else:
            return collatz_counter(odd_collatz(initialNumber), length)

print(collatz_counter(13, 1))

печатает 10.

person Terry Jan Reedy    schedule 20.08.2016