Проблема с изменяемой областью в Python

Question

Я новичок в Python, и я работал с ним немного, но я застрял в проблеме. Вот мой код:

def collatz(num,ctr): 
    if(num != 1): 
     ctr+=1 
     if(num%2==0): 
      collatz(num/2,ctr) 
     else: 
      collatz(num*3+1,ctr) 
    return ctr 
test=collatz(9,0) 

Для любого числа я кладу в течение num, скажем 9 к примеру, и 0 для ctr, ctr всегда выходит как 1. Я использую переменную ctr неправильно?

EDIT: Я пытаюсь распечатать, сколько раз функция рекурсивно. Таким образом, ctr будет счетчиком для каждой рекурсии.

Answer 1

переменная ctr в вашем примере всегда будет 1 из-за порядка рекурсивного стека вызовов. Когда возвращается одно значение ctr, тогда стек вызовов начнет возвращать предыдущие значения ctr. В основном, при самом последнем рекурсивном вызове будет возвращено самое высокое значение ctr. Но так как вызов метода в нижней части стека вызовов возвращает самое последнее значение, а также значение, которое будет храниться в test, test всегда будет 1. Предположим, что я вводил параметры в collatz, что привело бы к пяти общим вызовам метода. Стек вызовов будет выглядеть следующим образом сходящих,

collatz returns ctr --> 5 
collatz returns ctr --> 4 
collatz returns ctr --> 3 
collatz returns ctr --> 2 
collatz returns ctr --> 1 //what matters because ctr is being returned with every method call 

Как вы можете видеть, независимо от того, сколько раз collatz называются, 1 всегда будут возвращены, так как вызов в нижней части стеки вызовов имеет ctr сравнявшись 1 ,

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

EDIT: Если вы хотите, чтобы ctr в итоге было числом рекурсивного вызова, тогда просто назначьте значение ctr значению вызова метода. Это должно выглядеть так:

def collatz(num,ctr): 
    if(num != 1): 
     ctr+=1 
     if(num%2==0): 
      ctr = collatz(num/2,ctr) 
     else: 
      ttr = collatz(num*3+1,ctr) 
    return ctr 
test=collatz(9,0) 

Answer 2

Я изменил рекурсивные вызовы, чтобы установить возвращаемое значение из рекурсивных вызовов в ctr. Как вы его написали, вы отбрасывали ценности, которые вы получили от рекурсии.

def collatz(num,ctr): 
    if(num != 1): 
      ctr+=1 
      if(num%2==0): 
        ctr=collatz(num/2,ctr) 
      else: 
        ctr=collatz(num*3+1,ctr) 
    return ctr 

test=collatz(9,0) 

Answer 3

Пример:.

def collatz(number): 

    if number % 2 == 0: 
     print(number // 2) 
     return number // 2 

    elif number % 2 == 1: 
     result = 3 * number + 1 
     print(result) 
     return result 

n = input("Give me a number: ") 
while n != 1: 
    n = collatz(int(n)) 

Answer 4

переменные возвращают конечное число последовательности Коллатца, начиная с любого номером, который вы положить в Коллатце гипотеза говорит, что это всегда будет 1

Answer 5

Параметры функции в Python передаются по значению, а не по ссылке. Если вы передадите число функции, функция получит копию этого номера. Если функция изменяет свой параметр, что изменения не будут видны вне функции:

def foo(y): 
    y += 1 
    print("y=", y) # prints 11 

x = 10 
foo(x) 
print("x=", x) # Still 10 

В вашем случае, самое прямое исправление сделать в CTR глобальную переменную. Это очень уродливо, потому что вам нужно сбросить глобальное значение обратно до 0, если вы хотите снова вызвать функцию collatz, но я показываю эту альтернативу, чтобы показать, что ваша логика правильная, за исключением бита передачи по ссылке. (Обратите внимание, что функция collatz ничего не возвращает, ответ находится в глобальной переменной).

ctr = 0 
def collatz(num): 
    global ctr 
    if(num != 1): 
     ctr+=1 
     if(num%2==0): 
       collatz(num/2) 
     else: 
       collatz(num*3+1) 

ctr = 0 
collatz(9) 
print(ctr) 

Поскольку Python не имеет хвостового-вызов-оптимизации, ваш текущий рекурсивный код аварии с переполнением стека, если последовательность Коллатца больше, чем 1000 шагов (это Питоны по умолчанию лимит стека). Вы можете избежать этой проблемы, используя цикл вместо рекурсии. Это также позволяет избавиться от этой сложной глобальной переменной. Конечный результат является немного более идиоматическим Python, на моем взгляде:

def collats(num): 
    ctr = 0 
    while num != 1: 
     ctr += 1 
     if num % 2 == 0: 
      num = num/2 
     else: 
      num = 3*num + 1 
    return ctr 

print(collatz(9)) 

Если вы хотите придерживаться с помощью рекурсивных функций, его обычно чист, чтобы избежать использования изменяемых назначений, как вы пытаетесь сделать. Вместо функций, которые являются «подпрограммами», которые изменяют состояние, превращают их в нечто более близкое к математическим функциям, которые получают значение и возвращают результат, который зависит только от входных данных. Если вы сделаете это, это может быть намного проще рассуждать о рекурсии. Я оставлю это упражнение, но типичный «скелет» рекурсивная функция должна иметь если заявление, которое проверяет для базового случая и рекурсивных случаев:

def collatz(n): 
    if n == 1: 
     return 0 
    else if n % 2 == 0: 
     # tip: something involving collatz(n/2) 
     return #??? 
    else: 
     # tip: something involving collatz(3*n+1) 
     return #???