indirect recursion（间接递归）的应用场景及存在意义解答

首先明确：不存在只能用间接递归实现的编程问题，理论上所有间接递归逻辑都可以通过增加状态标记、合并逻辑的方式改写为直接递归。但在大量实际开发场景中，间接递归可以让代码逻辑更自然、可读性和可维护性更高，硬拆成直接递归反而会增加编码和维护成本。

常见的间接递归适用场景 #

1. 嵌套结构解析（最典型的是语法分析场景） #

处理有嵌套依赖的语法结构时，间接递归是最符合直觉的实现方式。比如四则运算表达式的解析，天然存在如下依赖关系：

• 表达式 = 项 + 加减运算符 + 项
• 项 = 因子 + 乘除运算符 + 因子
• 因子 = 数字 | 括号包裹的表达式

这种互相调用的逻辑用间接递归实现非常简洁，要是硬合并成单个直接递归函数，需要额外加大量状态参数判断当前解析阶段，代码会变得十分臃肿。
简化示例：

// 假设已经实现了获取当前token、消耗当前token的工具函数
int parse_expr();
int parse_term();
int parse_factor();

int parse_factor() {
    int val;
    if (current_token == TOKEN_LPAREN) {
        consume(TOKEN_LPAREN);
        val = parse_expr(); // 间接递归调用回parse_expr
        consume(TOKEN_RPAREN);
    } else {
        val = current_token.value;
        consume(TOKEN_NUMBER);
    }
    return val;
}

int parse_term() {
    int val = parse_factor();
    while (current_token == TOKEN_MUL || current_token == TOKEN_DIV) {
        int op = current_token.type;
        consume(op);
        int factor_val = parse_factor();
        val = op == TOKEN_MUL ? val * factor_val : val / factor_val;
    }
    return val;
}

int parse_expr() {
    int val = parse_term();
    while (current_token == TOKEN_ADD || current_token == TOKEN_SUB) {
        int op = current_token.type;
        consume(op);
        int term_val = parse_term();
        val = op == TOKEN_ADD ? val + term_val : val - term_val;
    }
    return val;
}

2. 交替执行的状态逻辑 #

如果业务逻辑天然是两个状态交替执行直到终止条件，用间接递归实现会比带状态标记的直接递归直观很多。比如回合制游戏的对战逻辑：

int player_hp = 100;
int enemy_hp = 100;

void player_turn();
void enemy_turn();

void player_turn() {
    if (enemy_hp <= 0) {
        printf("玩家胜利");
        return;
    }
    // 玩家攻击逻辑，扣除敌人血量
    enemy_hp -= rand() % 20;
    enemy_turn(); // 调用敌人回合
}

void enemy_turn() {
    if (player_hp <= 0) {
        printf("敌人胜利");
        return;
    }
    // 敌人攻击逻辑，扣除玩家血量
    player_hp -= rand() % 15;
    player_turn(); // 调用玩家回合
}

这个逻辑要是改成直接递归，需要额外加一个is_player_turn的状态参数，每次递归修改状态，可读性远不如间接递归的实现。

3. 复杂递归逻辑拆分 #

当单个递归函数的逻辑过于庞大，包含多个独立的递归分支时，可以把不同分支的逻辑拆成独立的函数，通过间接递归调用，方便单独调试、修改和复用。

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