Рекурсивная функция (последовательность скобок) - PullRequest
Новая
       4

Рекурсивная функция (последовательность скобок)

0 голосов
/ 23 января 2020

Это не мое решение, но я хочу знать, как оно работает. Поместите print в функцию. Задача: Найти всю правильную последовательность скобок, где длина 2 ⋅ n. Только круглые скобки. 

def foo(search, left, right, pairs):
    if left == pairs and right == pairs:
        print(search)
    else:
        print(left, right, 'else',)
        if left < pairs:
            print(left, right,'left')
            foo(search + '(', left + 1, right, pairs)
        if right < left:
            print(left, right, 'right')
            foo(search + ')', left, right + 1, pairs)

foo('', 0, 0, 3)

До первой правильной генерации последовательности все ясно. Но рядом есть несколько вопросов. Есть prints от первого до второго правильного поколения: 

((()))
2 0 right
2 1 else
2 1 left
3 1 else
3 1 right
3 2 else
3 2 right
(()())

Почему в первом print после первой правильной последовательности left, right = 2, 0?

1 Ответ

1 голос
/ 23 января 2020

Это из-за раскручивания стека рекурсии. Каждый раз, когда вы вызываете foo от первого, если l oop 

if left < pairs:

Второй, если l oop of (right

Один из способов увидеть стеки - это изменить первое условие l oop следующим образом: 

    if left < pairs:
        print(left, right,'left')
        print ("stacked -", ( left, right, 'right'))
        foo(search + '(', left + 1, right, pairs)
        # next if loop will be called once this foo returns
    if right < left:
        print(left, right, 'right')
        foo(search + ')', left, right + 1, pairs)

Он выведет значение left, right, для которого ему еще нужно go через следующий, если случай, но ожидая возврата из вызова foo сначала, если l oop. Я понимаю, что это немного сбивает с толку, но вы можете добавить больше операторов печати, чтобы увидеть, как это работает.

например, пример вывода: 

(0, 0, 'else')
(0, 0, 'left')
('stacked -', (0, 0, 'right'))
(1, 0, 'else')
(1, 0, 'left')
('stacked -', (1, 0, 'right'))
(2, 0, 'else')
(2, 0, 'left')
('stacked -', (2, 0, 'right'))
(3, 0, 'else')
(3, 0, 'right')
(3, 1, 'else')
(3, 1, 'right')
(3, 2, 'else')
(3, 2, 'right')
((()))
(2, 0, 'right')

Теперь, если вы видите в этом выводе, последний стек был для ('stacked -', (2, 0, 'right')), поэтому, когда он раскручивается это будет выполнено первым.

...