递归函数中的全局计数

Question

我看了一段关于河内大厦的视频，然后跟着写剧本来解决这个问题。代码运行得很好，但是我想在函数中添加一个计数器，这样我就可以用索引打印每一步，然后继续执行。

我尝试使用一个全局变量来计算调用递归函数的次数，并使用此计数作为我的索引，但仍然无法使它正常工作。我在这里做错什么了？

count = 0


def tower(n, start, end, middle):
    global count
    if n == 1:
        count += 1
        print('%i - Coloque o disco %i do pino %s no pino %s' % (count, n, start, end))
    else:
        count += 1
        tower(n - 1, start, middle, end)
        print('%i - Coloque o disco %i do pino %s no pino %s' % (count, n, start, end))
        tower(n - 1, middle, end, start)


tower(5, 'A', 'C', 'B')

现在输出是这样的：

5 - Coloque o disco 1 do pino A no pino C
5 - Coloque o disco 2 do pino A no pino B
6 - Coloque o disco 1 do pino C no pino B
6 - Coloque o disco 3 do pino A no pino C
8 - Coloque o disco 1 do pino B no pino A
8 - Coloque o disco 2 do pino B no pino C
9 - Coloque o disco 1 do pino A no pino C
9 - Coloque o disco 4 do pino A no pino B
12 - Coloque o disco 1 do pino C no pino B
12 - Coloque o disco 2 do pino C no pino A
13 - Coloque o disco 1 do pino B no pino A
13 - Coloque o disco 3 do pino C no pino B
15 - Coloque o disco 1 do pino A no pino C
15 - Coloque o disco 2 do pino A no pino B
16 - Coloque o disco 1 do pino C no pino B
16 - Coloque o disco 5 do pino A no pino C
20 - Coloque o disco 1 do pino B no pino A
20 - Coloque o disco 2 do pino B no pino C
21 - Coloque o disco 1 do pino A no pino C
21 - Coloque o disco 3 do pino B no pino A
23 - Coloque o disco 1 do pino C no pino B
23 - Coloque o disco 2 do pino C no pino A
24 - Coloque o disco 1 do pino B no pino A
24 - Coloque o disco 4 do pino B no pino C
27 - Coloque o disco 1 do pino A no pino C

有人能解释一下为什么柜台的工作方式不像我所说的那样吗？

Answer 1

问题是，当n == 1是递归时，您就开始打印它，但是每次调用递归时都会添加计数。

只需将count移到else语句中的打印之前，就可以解决这个问题，如下所示：

count = 0


def tower(n, start, end, middle):
    global count
    if n == 1:
        count += 1
        print('%i - Coloque o disco %i do pino %s no pino %s' % (count, n, start, end))
    else:
        tower(n - 1, start, middle, end)
        count += 1
        print('%i - Coloque o disco %i do pino %s no pino %s' % (count, n, start, end))
        tower(n - 1, middle, end, start)


tower(5, 'A', 'C', 'B')

它的产出如下：

1 - Coloque o disco 1 do pino A no pino C
2 - Coloque o disco 2 do pino A no pino B
3 - Coloque o disco 1 do pino C no pino B
4 - Coloque o disco 3 do pino A no pino C
5 - Coloque o disco 1 do pino B no pino A
6 - Coloque o disco 2 do pino B no pino C
7 - Coloque o disco 1 do pino A no pino C
8 - Coloque o disco 4 do pino A no pino B
9 - Coloque o disco 1 do pino C no pino B
10 - Coloque o disco 2 do pino C no pino A
11 - Coloque o disco 1 do pino B no pino A
12 - Coloque o disco 3 do pino C no pino B
13 - Coloque o disco 1 do pino A no pino C
14 - Coloque o disco 2 do pino A no pino B
15 - Coloque o disco 1 do pino C no pino B
16 - Coloque o disco 5 do pino A no pino C
17 - Coloque o disco 1 do pino B no pino A
18 - Coloque o disco 2 do pino B no pino C
19 - Coloque o disco 1 do pino A no pino C
20 - Coloque o disco 3 do pino B no pino A
21 - Coloque o disco 1 do pino C no pino B
22 - Coloque o disco 2 do pino C no pino A
23 - Coloque o disco 1 do pino B no pino A
24 - Coloque o disco 4 do pino B no pino C
25 - Coloque o disco 1 do pino A no pino C
26 - Coloque o disco 2 do pino A no pino B
27 - Coloque o disco 1 do pino C no pino B
28 - Coloque o disco 3 do pino A no pino C
29 - Coloque o disco 1 do pino B no pino A
30 - Coloque o disco 2 do pino B no pino C
31 - Coloque o disco 1 do pino A no pino C

Answer 2

重复条件可能比重复计数和打印更短：

conta = 0
def tower(disco, doPino, noPino, tempPino):
    global conta    
    if disco>1: tower(disco - 1, doPino, tempPino, noPino)
    conta += 1
    print(f'{conta} - Coloque o disco {disco} do pino {doPino} no {noPino}')
    if disco>1: tower(disco - 1, tempPino, noPino, doPino)

通过将打印和计数放在两个递归调用之间，在将磁盘n从start迁移到end之前需要完成的所有操作都将在打印移动本身之前打印(并计数)。在第二次递归调用之后，需要进行的所有其他操作都会被打印出来。当n为1时，顶部没有光盘，因此该函数只需打印和计数单个移动。

在这种情况下，第一个调用是将磁盘5从'A‘移动到'C’。但在此之前，每个光盘的顶部，光盘5需要移动到'B‘。所以我们让第一个递归调用来完成这个任务。然后我们打印移动(光盘5从'A‘到'C')。这将在'B‘位置留下一堆光盘( 1,2,3,4 )，因此第二次递归调用将处理从'B’到'C‘的移动磁盘1，2，3，4，并在移动光盘5之后打印。

简而言之，要将光盘1,2,3,4,5从“A”移动到“C”，我们有：

tower(5,'A','C','B'):
    # perform/print/count all moves to get discs 1,2,3,4 from 'A' to 'B'
    # print/count move disc 5 from 'A' to 'C'
    # perform/print/count all moves to get discs 1,2,3,4 from 'B' to 'C'