логическая рекурсия в python

Question

Я пытаюсь понять, является ли а степенью b. Чтобы это было верно, a должно делиться на b, а a / b также должно быть степенью b. Я борюсь с рекурсией здесь, похоже, она будет продолжаться вечно. Кто-нибудь может помочь?

def is_power(a,b):
    if(a % b == 0):
        a = a/b
        if(is_power(a,b)):
            return True
    return False

Answer 1

Что вам не хватает, так это базовый случай, который может вернуть True. Ваша функция возвращает True, только если рекурсивный вызов той же функции возвращает True. Что может произойти, только если другой рекурсивный вызов той же функции вернет True. Который может ... и так далее. Таким образом, единственное, что может произойти, это возвращение False или повторение навсегда (или, скорее, повторение 1000 раз, пока вы не получите исключение).

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

Один очевидный базовый случай - либо a == b, либо a == 1. Если любое из этих значений истинно, то вы знаете, что a - это степень b (первая или нулевая степень соответственно), поэтому вы можете немедленно вернуть True. Итак, давайте попробуем один из них:

def is_power(a,b):
    if a == b:
        return True
    if(a % b == 0):
        a = a/b
        if(is_power(a,b)):
            return True
    return False

Теперь это работает для многих значений - is_power(16, 2), is_power(6561, 3) и т. Д.

Но, если это не Python 2, есть еще одна проблема: a/b возвращает число с плавающей запятой, а не int, что означает, что ваш следующий рекурсивный шаг может из-за проблем с округлением с плавающей запятой вычислить a % b и получить что-то вроде 1e -302 вместо 0, поэтому a % b == 0 будет ложным, и вы зайдете слишком далеко и продолжите деление. Это в конечном итоге достигнет 0 и, наконец, вернет True (правильный ответ по неправильной причине), но если для этого потребуется более 1000 шагов, сначала вы достигнете предела рекурсии и вызовете исключение.

Чтобы это исправить, просто используйте // вместо /.

Answer 2

def is_power(a,b):
    if(a % b == 0):
        a = a/b
        return a == 1 or is_power(a,b)
    return False

Answer 3

Альтернативный подход - взять логарифм a по отношению к основанию b. Если результатом является целое число, то b**x = a для некоторых x

from math import log

def is_power(a, b):
    return log(a, b).is_integer()

Answer 4

Если mod равно 0, вы должны продолжать рекурсию до тех пор, пока a / b не станет равным 1 (то есть равно):

def is_power(a,b):
    if(a % b == 0):
        a = a/b
        if(a == 1):
            return True
        else:
            return is_power(a,b)
    else:
      return False

print(is_power(16,2))
True

Answer 5

Вам нужно условие выхода:

def is_power(a,b):
    if a == b:
        return True
    elif a % b == 0:
        a = a/b
        return is_power(a,b)
    return False