c++ - 間接再帰の実用化

Question

インタビューで、彼らは私に「間接再帰の実用的なアプリケーションをいくつか教えてください」と尋ねました。直接再帰と間接再帰の違いを答えただけです。私はグーグルで検索しましたが、満足のいく答えはまだ得られませんでした。

このトピックに関する情報は大歓迎です..

Answer 1

ところで、相互再帰という名前でそれを知っていました。

有限オートマトンをシミュレートするために使用できますが、言語が末尾呼び出しの最適化を実装している場合にのみ使用できます。つまり、1 つの再帰呼び出しが、さらなる再帰呼び出しのみで構成される return ステートメントで終了した場合、その再帰呼び出しは現在のスタック フレームを再利用します。この最適化を行わないと、相互再帰によって簡単にスタック オーバーフローが発生する可能性があります (駄洒落 ... :-)。

より明確にするために111、入力文字列内の文字列の最初の出現を認識する Lua スクリプトを次に示します。各関数は有限オートマトンの状態を表し、状態遷移は相互再帰呼び出しによってシミュレートされます (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 )