рекурсивная функция python 3 «превышена максимальная глубина рекурсии»

Я создаю последовательность коллатца с рекурсивной функцией ниже:

def collatz(n):
  if n%2 == 0:
    return int(n/2)
  else:   
    return int((3 * n)/2)

Насколько я понимаю, рекурсивная функция — это функция, которая в основном вызывает сама себя. Ниже я попытался создать рекурсивную функцию со следующим:

def collatz(x):
    if x == 1:
        "Done"
    print(x)
    x = collatz(x)
    return(x)

Где, по существу, переменная x продолжает передаваться в функцию collatz, которую я определил, пока не достигнет 1. Однако каждый раз, когда я запускаю рекурсивную функцию, она повторно печатает 'x', а затем я получаю

collatz(3)    
'RecursionError: maximum recursion depth exceeded in comparison'

Как я понимаю, это бесконечный цикл. Я думал, что, переназначив его на x для результатов первого collatz(), он вернет новое значение и будет продолжаться до тех пор, пока не достигнет '1', но я, похоже, не совсем понял.

Любая помощь/советы/советы были бы замечательными! Спасибо!


python-3.x python function recursion collatz
person Harris2018    schedule 08.10.2017    source источник
comment
Вы получаете ошибку, потому что вы вызываете функцию из определения — вы не закончили определение функции, и вы должны вызывать ее извне функции (отступ).   -  person    schedule 08.10.2017
comment
Я не совсем понимаю ваше объяснение. Какая часть функции не определена? Я только что отредактировал исходный пост, показав, где я вызываю функцию Collatz.   -  person Harris2018    schedule 08.10.2017
comment
Печатаю на мобильном телефоне, извиняюсь... у вас есть collatz(x) внутри функции collatz, отсюда и ошибка. Вызывайте collatz(x) вне функции, то есть не делайте отступ, чтобы он был частью функции, которую вы определяете.   -  person    schedule 08.10.2017
comment
Вы обнаружите, что не воспроизвели свой пример функции. Будет обновляться, когда рядом с компьютером.   -  person    schedule 08.10.2017
comment
@mikey он, очевидно, делает это, поскольку, если бы это было не так, ошибка, которую он наблюдает, - это отсутствие вывода.   -  person Adam Smith    schedule 08.10.2017
comment
Я думал, что весь смысл рекурсии в том, чтобы иметь возможность перебирать функцию, не так ли? Я следовал этому минимально воспроизводимому примеру (python-course.eu/recursive_functions.php)   -  person Harris2018    schedule 08.10.2017
comment
первая функция коллатца работает и дает мне первое число в последовательности, я хотел использовать рекурсию, чтобы получить все остальные числа в последовательности и остановиться на 1   -  person Harris2018    schedule 08.10.2017
comment
Н.Б. что нечетный случай коллаца - это 3n+1, а не 3n / 2   -  person Adam Smith    schedule 08.10.2017
comment
Если вы пройдёте через то, что видите в коде, вы поймёте, что этому нет конца. collatz всегда переходит в collatz. x никогда не уменьшается.   -  person Chris    schedule 08.10.2017

Ответы (3)


arrow_upward
0
arrow_downward

Вы показываете две разные реализации одной и той же функции collatz, при этом вам нужно их объединить.

def collatz(n):
    if x == 1:
        "Done"
    print(x)
    if n%2 == 0:
        collatz(int(n/2))
    else:   
        collatz(int((3 * n)/2))
person Roee Gavirel    schedule 08.10.2017

arrow_upward
2
arrow_downward

Рекурсивные функции имеют то, что известно как «базовый случай» и то, что известно как «рекурсивный случай». В базовом случае следует прекратить рекурсию и вернуть ответ.

В этом случае базовым случаем является случай, когда x==1

def collatz(x):
    if x == 1:
        return x

а рекурсивный случай - все остальное время

# continuing from above
    else:
        if n % 2 == 0:
            return collatz(int(n//2))
        else:
            return collatz(n*3 / 2)  # sicut. Note that the collatz sequence
                                     # uses 3n+1 here, not 3n/2 as in the question

Н.Б. что я изменяю действующее значение x в следующем цикле через collatz, прежде чем возвращать результат этого нового вызова. Если вы этого не сделаете и просто return collatz(x), вы никогда не достигнете своего базового случая и будете рекурсивно работать вечно.

person Adam Smith    schedule 08.10.2017
comment
Рекурсия также является тем, что Python делает особенно плохо по сравнению с другими современными языками. Это полезная концепция, но по возможности старайтесь избегать ее в рабочем коде. См. эту реализацию в haskell. - person Adam Smith; 08.10.2017
comment
отметил - это было больше для практики/обучения, чем что-либо еще, но я ценю помощь! - person Harris2018; 08.10.2017
comment
@ Harris2018 Я понимаю. Рекурсия совершенно необходима, чтобы научиться иметь более широкое понимание разработки программного обеспечения, но в Python отсутствуют определенные оптимизации для рекурсии (главным образом среди них устранение хвостовых вызовов), что делает ее в целом плохой идеей для любого не игрушечного кода, если вы можете избежать этого. - person Adam Smith; 08.10.2017
comment
например, последовательность коллатца, тогда, если мне нужно создать другую последовательность по шаблону, лучше ли сделать это через цикл и избежать рекурсии? Что лучше всего, я склонен работать с большими наборами данных и не хочу тратить время/память/ресурсы - person Harris2018; 08.10.2017
comment
@ Harris2018 определенно предпочитает итеративные последовательности рекурсивным, да. В этом случае я бы сделал нечто вот так - person Adam Smith; 08.10.2017

arrow_upward
1
arrow_downward

@Рои Гавирел

Вот окончательный ответ, основанный на его ответе выше:

def collatz(x):
    if x == 1:
        "Done"
    elif x%2 == 0:
        x = int(x/2)
        print(x)
        collatz(x)     
    else:
        x = int((3*x)+1)
        print(x)
        collatz(x)


collatz(3)

Спасибо за помощь!

person Harris2018    schedule 08.10.2017