Как пользоваться рекурсией в Python?

Question

[Андрей Носов]

Добрый вечер.
Знаю, что выкладывать большие куски кода - это свинство, но иначе не получится. Есть функция:

def check_possibility(figures, signs = [], is_100 = False):
    for sign in ('', '+', '-', '*', '//', '**'):
        signs.append(sign)
        if len(signs) == 5:
            numeric_expression = ''
            numeric_expression += figures[0]
            for i in range(5):
                numeric_expression += signs[i]
                numeric_expression += figures[i + 1]
            result = eval(numeric_expression)
            if result == 100:
                return numeric_expression
            else:
                return False
        elif is_100 == False:
            is_100 = check_possibility(figures, signs, is_100)
    return is_100

Она принимает список из 6 цифр (цифры в строковом представлении).
По задумке эта функция должна с помощью рекурсии перебирать все возможные комбинации знаков (или их отсутствие), расставлять между цифрами и проверять, равняется ли полученное выражения 100.
Интерпретатор возвращает это:
Traceback (most recent call last):
File "D:\Дмитрий\Documents\Python\programs\def.py", line 46, in
main()
File "D:\Дмитрий\Documents\Python\programs\def.py", line 42, in main
numeric_expression = check_possibility(number_list)
File "D:\Дмитрий\Documents\Python\programs\def.py", line 32, in check_possibility
Последнюю строку дублирует бесконечно.
Подозреваю, что в этой функции неверно все. Не могли бы вы объяснить, как мне создать верную функцию (или даже исправить старую).

Comments

[tsarevfs]

Используйте отладочную печать. print signs в начале функции должно вас навести на мысль. Проблема действительно в том что у вас массив по ссылке передается. Нужно явно скопировать, например используя срез: is_100 = check_possibility(figures, signs[:], is_100).

[tsarevfs]

"Знаю, что выкладывать большие куски кода - это свинство." Это не куча =) Больше задалбывает каждый раз просить выложить код в котором ошибка и сам текст ошибки. Так что у вас как раз нормальный вопрос.

[Андрей Носов]

tsarevfs: После того, как я исправил код (передаю срез массива), комбинации, где невозможно получить 100, корректно возвращают False, а комбинации, где это возможно, выводят все ту же ошибку.

Answer 1

[tsarevfs]

def check_possibility(figures, signs = [], is_100 = False):
    for sign in ('', '+', '-', '*', '//'):
        new_signs = signs[:]
        new_signs.append(sign)
        if len(signs) == 5:
            numeric_expression = ''
            numeric_expression += figures[0]
            for i in range(5):
                numeric_expression += signs[i]
                numeric_expression += figures[i + 1]
            result = eval(numeric_expression)
            if result == 100:
                return numeric_expression
            else:
                return False
        elif is_100 == False:
            is_100 = check_possibility(figures, new_signs, is_100)
    return is_100

print check_possibility([str(n) for n in range(2, 8)])

ps. ** опасная операция будет очень долго считать если попадутся большие аргументы. python считает в длинной арифметике для целых.

Comments

[Андрей Носов]

Теперь функция корректно обрабатывает случаи, где нельзя получить 100 и возвращает False, но если 100 получить можно, возникает все та же ошибка.

[tsarevfs]

Дмитрий Тычинин: вставил полный код, который работает у меня.

[tsarevfs]

Дмитрий Тычинин: да, еще не рекомендуется делать параметр по умолчанию = []. https://habrahabr.ru/post/50381/

[sim3x]

tsarevfs: также как дикт и обьект

Answer 2

[#алгоптимизируй #отботизируй]

signs передается как копия или по ссылке?
Под отладчиком гляньте,а код - это хорошо, взял и запустил, (пока не могу)
В этом коде не вижу перебор разной последовательности этих знаков