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

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.

解决了一个名为 Tower of Hanoi 的问题

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

一些问题：

为什么它的行为像线程一样？
为什么一开始从4倒数到1，后来又倒数？
为什么第一步不是从A到C，而是从A到B？
递归在现实生活中真的有用吗？根据我的阅读，它是：
- (-)资源昂贵
- (-)较慢
- (+)更容易实现

Answer 1

我无法回答你所有的问题，但我可以回答：

Why the first move is not from A to C, instead, it is from A to B?

假设n=2，第一步是将A移动到B，步骤如下：

FIRST RECURSOR Move from A to B
START THE SHOW Move from A to C
SECOND RECURSOR Move from B to C

或者我们可以通过这些步骤将塔移到 B

FIRST RECURSOR Move from A to C
START THE SHOW Move from A to B
SECOND RECURSOR Move from C to B

这样我们就证明了我们可以将顶部的两个块移动到任何位置。让我们考虑一下 n=3 的情况。我们可以将顶部的两个块移动到 B 或 C 中的任何一个。但是，要为第三个块保留 C 空闲，我们需要将顶部的两个块移动到 B。如下所示：

FIRST RECURSOR Move from A to C
FIRST RECURSOR Move from A to B
SECOND RECURSOR Move from C to B

START THE SHOW Move from A to C
FIRST RECURSOR Move from B to A
SECOND RECURSOR Move from B to C
SECOND RECURSOR Move from A to C

我们可以再次将前三个块移动到 B 或 C，因为我们可以将前两个块移动到 B 或 C。此逻辑递归应用，这意味着每个奇数的汉内塔的解决方案以A到C开头的盘子数，偶数个盘子有一个以A到B开头的解。

Answer 2

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

如您所写，函数 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))
    )
)

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

Logic behind recursive functions that calls itself more than once in itself

python

recursion

towers-of-hanoi