От двоичного к десятичному в Python (изменение кода для рекурсивного?)

Question

На прошлой неделе одна из моих домашних работ заключалась в том, чтобы запрограммировать метод Python, который получает двоичный файл в виде массива в параметрах, а затем в результате возвращает указанный двоичный файл в десятичное.

Я пытался найти рекурсивное решение, но время истекало до крайнего срока и не решало это рекурсивным способом. Возможно, решение простое. Как я могу это сделать?

Моей последней ставкой на входящие сообщения учителя была эта часть кода:

def binToDec (arr):
    arr.reverse()
    result = 0
    for x in range(0,len(arr)):
        result+=arr[x]*pow(2,x)
    return result

arr = [1,1,0,0] 
result = binToDec(arr)
print (arr)
print (result)

Answer 1

Все циклы можно преобразовать в хвостовую рекурсию.

def bin_to_dec(arr):
    if not arr:
        return 0
    return arr[-1] + (bin_to_dec(arr[:-1]) << 1)


print(bin_to_dec([1, 1, 0, 0]))

Вывод:

12

---

Если вы запутались с индексами, вот более читаемый код:

def bin_to_dec(arr):
    if not arr:
        return 0
    *rest, lsb = arr
    return lsb + (bin_to_dec(rest) << 1)

тот же вывод, что и выше.

Answer 2

Во-первых, обычно считается плохой практикой инвертировать входной массив как побочный эффект. И pow действительно излишне здесь. ИМХО, итерационная функция была бы более Pythoni c таким образом:

def binToDec (arr):
    result = 0
    coeff = 1
    for x in reversed(arr):
        result+=x*coeff
        coeff *=2
    return result

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

def recursBinToDec(arr):
    if 0 == len(arr):
        return 0
    else:
        return arr[-1] + 2 * recursBinToDec(arr[:-1])

Answer 3

Для рекурсивного кода, посмотрите эту ссылку https://www.geeksforgeeks.org/recursive-program-for-binary-to-decimal/

Существует графическое представление, которое показывает, как мы должны добавить все значения. Поэтому мы берем текущее значение, добавляем его, а затем повторяем для остальных элементов. Код ссылки довольно понятен.