间接递归的实际应用

Question

在一次采访中,他们让我"给出一些间接递归的实际应用".我只是回答了直接递归和间接递归之间的区别.我用谷歌搜索,但仍然没有得到任何令人满意的答案.

有关此主题的任何信息都是最受欢迎的..

Answer 1

间接递归的一个明显示例是递归下降解析器.

举个简单的例子,考虑一个语法:

expression = product (+|-) product

product  = term (*|/) term

term = number | variable | '(' expression ')'

要使用递归下降解析器解析该语法,我们基本上创建一个函数来表示每个元素:

expression(input) { 
    product(input);
    assert(operator(input) == '-' || '+');
    product(input);
}

product(input) {
    term(input);
    assert(operator(input) == '/' || '*');
    term(input);
}

term(input) { 
    if (next(input) == '(')
        expression(input);
    // ...
}

我显然在这里简化了许多,但希望总体思路出现:表达式由+或者组合的产品组成-.产品由/或组合的术语组成*.术语是括号中的数字或变量或表达式.我们调用一个函数来识别每个函数,所以当我们将括号中的表达式识别为术语时,我们使用间接递归 - expression()- > product()- > term()- > expression().