practical application of indirect recursion [closed]

Question

In an interview they asked me to "give some practical applications of indirect recursion". I just replied the difference between direct recursion and indirect recursion. I googled but still didn't get any satisfying answers.

Any information on this topic is most welcome..

Answer 1

One obvious example of indirect recursion is a recursive descent parser.

For a simple example, consider a grammar something like:

expression = product (+|-) product

product  = term (*|/) term

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

To parse that grammar with a recursive descent parser, we basically create a function to represent each element:

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

I'm obviously simplifying a lot here, but hopefully the general idea comes though: an expression is composed of products combined by + or -. A product is composed of terms combined by / or *. A term is a number or a variable or an expression enclosed in parentheses. We call a function to recognize each of those, so when we're recognizing an expression in parentheses as a term, we use indirect recursion -- expression() -> product() -> term() -> expression().

Answer 2

BTW, I knew it under the name of mutual recursion.

It can be used to simulate finite automata, but only if the language implements tail call optimization, which means that when one recursive call terminates with a return statement consisting solely of a further recursive call, that recursive call reuses the current stack frame. Without this optimization the mutual recursion could easily lead to Stack Overflow (pun ... well :-).

To be more explicit, here is a Lua script that recognizes the first occurrence of the string 111 inside the input string. Each function represent a state of the finite automaton and state transitions are simulated by mutually recursive calls (Lua performs proper tail call optimization, so stack overflow won't happen even for much longer input strings). In C++ the same technique is not applicable, since proper tail call optimization is not guaranteed by the standard (AFAIK). If you don't know Lua, take it as pseudo code (it is fairly readable, since it has a Pascal-like syntax). Anyway you can cut and paste the code in the live demo.

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 )