python - 多次调用自身的递归函数背后的逻辑

Question

我理解只有一个嵌套函数的递归函数，例如这个:

def recurseInfinitely( n ):   
    try:
        recurseInfinitely(n+1)
    except RuntimeError:
        print("We got to level %s before hitting the recursion limit." % n)

该函数会调用自身直到遇到障碍，即 998 次。

但是当一个函数调用自身两次时，事情会让我感到非常困惑。

这个问题的灵感来自于 youtube 上的一个视频，该视频解释了递归并使用 Python 解决了一个名为 汉诺塔 的问题。

Recursion 'Super Power' (in Python) - Computerphile

我将功能更改为:

def move(x, y, name):
    print("   {} Move from {} to {}".format(name, x,y))

def hanoi(n_of_disks,from_position,helper_position,target_position, name):
    if n_of_disks==0:
        print("#name: %s do nothing if there's no disk: %d" % (name, n_of_disks))
        pass
    else:
        # --> A
        print("Before A, name: %s disk: %d" % (name, n_of_disks))
        hanoi(n_of_disks-1,  # 3
            from_position,   # A
            target_position, # C
            helper_position, # B
            name='FIRST RECURSOR') 

        move(from_position,  # A
            target_position, # C
            name) 

        # --> B
        print("Before B, name: %s disk: %d" % (name, n_of_disks))
        hanoi(n_of_disks-1,  # 3
            helper_position, # B
            from_position,   # A
            target_position, # C
            name='SECOND RECURSOR') 

然后运行它...

hanoi(n_of_disks=4,
      from_position='A',
      helper_position='B',
      target_position='C',
      name="START THE SHOW")

结果是:

Before A, name: START THE SHOW disk left: 4
Before A, name: FIRST RECURSOR disk left: 3
Before A, name: FIRST RECURSOR disk left: 2
Before A, name: FIRST RECURSOR disk left: 1
#name: FIRST RECURSOR do nothing if there's no disk: 0
   FIRST RECURSOR Move from A to B
Before B, name: FIRST RECURSOR disk left: 1
#name: SECOND RECURSOR do nothing if there's no disk: 0
   FIRST RECURSOR Move from A to C
Before B, name: FIRST RECURSOR disk left: 2
Before A, name: SECOND RECURSOR disk left: 1
#name: FIRST RECURSOR do nothing if there's no disk: 0
   SECOND RECURSOR Move from B to C
Before B, name: SECOND RECURSOR disk left: 1
#name: SECOND RECURSOR do nothing if there's no disk: 0
   FIRST RECURSOR Move from A to B
Before B, name: FIRST RECURSOR disk left: 3
Before A, name: SECOND RECURSOR disk left: 2
Before A, name: FIRST RECURSOR disk left: 1
#name: FIRST RECURSOR do nothing if there's no disk: 0
   FIRST RECURSOR Move from C to A
Before B, name: FIRST RECURSOR disk left: 1
#name: SECOND RECURSOR do nothing if there's no disk: 0
   SECOND RECURSOR Move from C to B
Before B, name: SECOND RECURSOR disk left: 2
Before A, name: SECOND RECURSOR disk left: 1
#name: FIRST RECURSOR do nothing if there's no disk: 0
   SECOND RECURSOR Move from A to B
Before B, name: SECOND RECURSOR disk left: 1
#name: SECOND RECURSOR do nothing if there's no disk: 0
   START THE SHOW Move from A to C
Before B, name: START THE SHOW disk left: 4
Before A, name: SECOND RECURSOR disk left: 3
Before A, name: FIRST RECURSOR disk left: 2
Before A, name: FIRST RECURSOR disk left: 1
#name: FIRST RECURSOR do nothing if there's no disk: 0
   FIRST RECURSOR Move from B to C
Before B, name: FIRST RECURSOR disk left: 1
#name: SECOND RECURSOR do nothing if there's no disk: 0
   FIRST RECURSOR Move from B to A
Before B, name: FIRST RECURSOR disk left: 2
Before A, name: SECOND RECURSOR disk left: 1
#name: FIRST RECURSOR do nothing if there's no disk: 0
   SECOND RECURSOR Move from C to A
Before B, name: SECOND RECURSOR disk left: 1
#name: SECOND RECURSOR do nothing if there's no disk: 0
   SECOND RECURSOR Move from B to C
Before B, name: SECOND RECURSOR disk left: 3
Before A, name: SECOND RECURSOR disk left: 2
Before A, name: FIRST RECURSOR disk left: 1
#name: FIRST RECURSOR do nothing if there's no disk: 0
   FIRST RECURSOR Move from A to B
Before B, name: FIRST RECURSOR disk left: 1
#name: SECOND RECURSOR do nothing if there's no disk: 0
   SECOND RECURSOR Move from A to C
Before B, name: SECOND RECURSOR disk left: 2
Before A, name: SECOND RECURSOR disk left: 1
#name: FIRST RECURSOR do nothing if there's no disk: 0
   SECOND RECURSOR Move from B to C
Before B, name: SECOND RECURSOR disk left: 1
#name: SECOND RECURSOR do nothing if there's no disk: 0

一些问题:

1. 为什么它的行为就像它的线程？
2. 为什么一开始从 4 倒数到 1，后来又从 4 倒数到 1？
3. 为什么第一步不是从A到C，而是从A到B？

4. 递归在现实生活中真的有用吗？据我所读，它是:

   • (-)资源昂贵
   • (-)较慢
   • (+)更容易实现

Answer 1

我不确定是否理解这段代码的目的，但我确实理解递归。

正如您所写，函数recurseInfinitely是一个终端递归函数。这意味着递归调用是函数中要完成的最后一个操作。因此，此类函数的执行是线性的:

recurseInfinitely(0)
└─ recurseInfinitely(1)
   └─ recurseInfinitely(2)
      └─ ...

相反，函数hanoi 不是终端递归，因为它调用了两次自身。执行看起来像一个二叉树。例如，n = 3:

hanoi(3,A,B,C)           3
├─ hanoi(2,A,C,B)        2
│  ├─ hanoi(1,A,B,C)     1
│  │  ├─ hanoi(0,A,C,B)  0
│  │  └─ hanoi(0,C,A,B)  0
│  └─ hanoi(1,C,A,B)     1
│     ├─ hanoi(0,C,B,A)  0
│     └─ hanoi(0,A,C,B)  0
└─ hanoi(2,B,A,C)        2
   ├─ hanoi(1,B,C,A)     1
   │  ├─ hanoi(0,B,A,C)  0
   │  └─ hanoi(0,C,B,A)  0
   └─ hanoi(1,A,B,C)     1
      ├─ hanoi(0,A,C,B)  0
      └─ hanoi(0,B,A,C)  0

这与您的结果相对应。

实际上，应该避免这种算法，因为它随着 n (~2^n) 指数级增长。

关于递归的有用性，递归资源消耗更大或更慢的说法并不正确。然而，事实是递归并不适合所有语言。事实上，有些语言完全基于递归(例如 Lisp、Scheme 和 SQL)。它被称为函数式编程，而且确实非常优雅。

例如，在Scheme中可以编写阶乘函数

(define (fact n)
    (if (zero? n)
        1
        (* n (fact (- n 1)))
    )
)

应该注意的是，该函数不是终端递归，因为它在递归调用后执行乘法。

它的终端版本(使用累加器)是

(define (fact n)
    (fact-acc n 1)
)

(define (fact-acc n acc)
    (if (zero? n)
        acc
        (fact-acc (- n 1) (* n acc))
    )
)