如何反转递归调用逻辑实现对应计数功能

递归执行天然分为两个阶段：向下递推（持续调用自身直到触达终止条件）、向上回溯（从终止条件逐层返回结果到最上层调用方）。你当前写的正常运行的递归计数，是把计数逻辑放在递推阶段执行，所谓反转逻辑，就是把计数逻辑挪到回溯阶段执行即可。

正向计数（你当前的实现逻辑） #

这类计数的特点是进入函数就累加，统计的是递推过程中总共触发的递归调用次数，典型实现如下（以阶乘递归为例）：

call_count = 0
def fact(n):
    global call_count
    call_count += 1  # 进入递归层立刻计数，属于递推阶段操作
    if n == 1:
        return 1
    return n * fact(n-1)

执行fact(5)后call_count值为5，对应5次递归调用。

反转后的计数逻辑 #

核心修改只有两点：

• 把计数累加操作从递归调用语句之前，移动到递归调用返回之后
• 递归终止分支不再直接返回，而是初始化计数的基准值

全局变量实现版本 #

backtrack_count = 0
def fact_reverse(n):
    global backtrack_count
    if n == 1:
        backtrack_count = 1  # 触达递归最底层时初始化计数基准
        return 1
    res = n * fact_reverse(n-1)
    backtrack_count += 1  # 等下层递归返回后再累加，属于回溯阶段操作
    return res

执行fact_reverse(5)后backtrack_count值为5，计数顺序是从最底层往上层累加，和正向计数的执行顺序完全相反。

无全局变量实现版本 #

如果不想用全局变量，可以把计数作为返回值的一部分，逐层向上传递汇总：

def fact_reverse_no_global(n):
    if n == 1:
        return 1, 1  # 第二个返回值为当前层计数，触底时基准值为1
    child_res, child_count = fact_reverse_no_global(n-1)
    current_count = child_count + 1  # 回溯阶段基于下层结果计算当前层计数
    return n * child_res, current_count

执行fact_reverse_no_global(5)会返回(120,5)，第二个值就是反转逻辑下的计数结果。

反转逻辑的计数通常用于统计递归深度、树结构子节点总数、回溯路径层级等需要从最底层向上汇总数值的场景，不需要额外新增栈或者队列存储中间状态，靠递归本身的回溯特性就能完成计算。

内容的提问来源于stack exchange，提问作者Adaptation