c++ - 间接递归的实际应用

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);
    // ...
}

我显然在这里简化了很多，但希望总的想法来了：表达式由+or组合的产品组成-。产品由/或组合的术语组成*。术语是括在括号中的数字或变量或表达式。我们调用一个函数来识别其中的每一个，因此当我们将括号中的表达式识别为术语时，我们使用间接递归 -- expression()-> product()-> term()-> expression()。

Answer 2

顺便说一句，我以相互递归的名义知道它。

它可以用来模拟有限自动机，但前提是该语言实现了尾调用优化，这意味着当一个递归调用以仅包含进一步递归调用的 return 语句终止时，该递归调用重用当前堆栈帧。如果没有这种优化，相互递归很容易导致堆栈溢出（双关语......好吧:-)。

更明确地说，这是一个 Lua 脚本，它识别111输入字符串中第一次出现的字符串。每个函数代表一个有限自动机的状态，并且状态转换是通过相互递归调用来模拟的（Lua 执行适当的尾调用优化，因此即使对于更长的输入字符串也不会发生堆栈溢出）。在 C++ 中，相同的技术不适用，因为标准 (AFAIK) 不能保证正确的尾调用优化。如果您不了解 Lua，请将其视为伪代码（它具有相当的可读性，因为它具有类似 Pascal 的语法）。无论如何，您可以在现场演示中剪切和粘贴代码。

function Init( input, pos )
    if pos > #input then return 0 end
    local bit = input:sub( pos, pos )
    if bit == "0" then
        return Got0( input, pos + 1 )
    else
        return Got1( input, pos + 1 )
    end
end

function Got0( input, pos )
    if pos > #input then return 0 end
    local bit = input:sub( pos, pos )
    if bit == "0" then
        return Got0( input, pos + 1 )
    else
        return Got1( input, pos + 1 )
    end
end

function Got1( input, pos )
    if pos > #input then return 0 end
    local bit = input:sub( pos, pos )
    if bit == "0" then
        return Got0( input, pos + 1 )
    else
        return Got11( input, pos + 1 )
    end
end

function Got11( input, pos )
    if pos > #input then return 0 end
    local bit = input:sub( pos, pos )
    if bit == "0" then
        return Got0( input, pos + 1 )
    else
        print( "recognized 111 sequence at position " .. pos - 2 )
        print( input )
        print( (" "):rep( pos - 3 ) .. "^" )
        return 1
    end
end

Init( "1101101101110110101", 1 )