https://reverseengineering.stackexchange.com/questions/18719/how-can-i-reverse-this-recursive-function/19287#19287

given.dot

strict digraph "" {
	graph [ordering="out"];
	null[label=""];
	C -> G;
	C -> H;
	G -> M;
	G -> N;
	F -> S;
	F -> U;
	H -> null;
	H -> W;
	J -> Z;
	J -> A;
	L -> P;
	L -> Y;
	O -> J;
	O -> K;
	P -> O;
	P -> E;
	S -> L;
	T -> F;
	T -> V;
	W -> X;
	W -> I;
	Z -> C;
	Z -> D;
}

given.svg

solve.py

debug = False


def the_process(stored, inp, size, fs):
    if debug:
        print '\t' * fs + \
            "the_process({}, {}, {})".format(stored, "".join(inp), size)
    idx = 0
    global thstr
    idx = stored.index(inp[0])
    if idx:
        the_process(stored[:idx], inp[1:], idx, fs + 1)
    if size - 1 != idx:
        the_process(stored[1 + idx:1 + idx + size - idx - 1],
                    inp[idx + 1:], size - idx - 1, fs + 1)
    thstr.append(inp[0])


def rev_process(stored, inp, size, fs):
    if debug:
        print '\t' * fs + \
            "rev_process({}, {}, {})".format(stored, "".join(inp), size)
    if not size:
        return
    global thstr
    mp = {stored[i]: i for i in xrange(len(stored))}
    idx = mp[inp[-1]]
    thstr.append(inp[-1])
    if size == 1:
        return
    try:
        less_part = max(
            loc for loc,
            val in enumerate(inp) if mp[val] < idx) + 1
    except ValueError:
        less_part = 0
    rev_process(stored[:idx], inp[:less_part], less_part, fs + 1)
    if less_part != size - 1:
        rev_process(stored[idx + 1:], inp[less_part:-1],
                    size - less_part - 1, fs + 1)


if __name__ == "__main__":
    thstr = []
    stored = "MGNCHXWIZDJAOKPELYSFUTV"
    input1 = "TFSLPOJZCGMNHWXIDAKEYUV"
    target = "MNGHCWZIJDXOPKLESUVTFYA"
    print "sample input  : " + input1
    the_process(stored, input1, 23, 0)
    output1 = "".join(thstr)
    print "sample output : " + output1
    thstr = []
    rev_process(stored, output1, 23, 0)
    input1_rev = "".join(thstr)
    assert input1 == input1_rev
    thstr = []
    print "target output : " + target
    rev_process(stored, target, 23, 0)
    target_rev = "".join(thstr)
    print "target input  : " + target_rev
    thstr = []
    the_process(stored, target_rev, 23, 0)
    target_out = "".join(thstr)
    assert target_out == target

target.dot

strict digraph "" {
	graph [ordering="out"];
    A -> X;
    X -> C;
    C -> G;
    G -> M;
    G -> N;
    C -> H;
    X -> D;
    D -> I;
    I -> W;
    I -> Z;
    D -> J;
    A -> Y;
    Y -> E;
    E -> K;
    E -> L;
    K -> O;
    K -> P;
    Y -> F;
    F -> S;
    F -> T;
    T -> U;
    T -> V;
}

target.svg

<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
 "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<!-- Generated by graphviz version 2.40.1 (20161225.0304)
 -->
<!-- Pages: 1 -->
<svg width="602pt" height="332pt"
 viewBox="0.00 0.00 602.00 332.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 328)">
<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-328 598,-328 598,4 -4,4"/>
<!-- A -->
<g id="node1" class="node">
<title>A</title>
<ellipse fill="none" stroke="#000000" cx="315" cy="-306" rx="27" ry="18"/>
<text text-anchor="middle" x="315" y="-302.3" font-family="Times,serif" font-size="14.00" fill="#000000">A</text>
</g>
<!-- X -->
<g id="node2" class="node">
<title>X</title>
<ellipse fill="none" stroke="#000000" cx="207" cy="-234" rx="27" ry="18"/>
<text text-anchor="middle" x="207" y="-230.3" font-family="Times,serif" font-size="14.00" fill="#000000">X</text>
</g>
<!-- A&#45;&gt;X -->
<g id="edge1" class="edge">
<title>A&#45;&gt;X</title>
<path fill="none" stroke="#000000" d="M295.6918,-293.1278C278.6445,-281.763 253.5981,-265.0654 234.4656,-252.3104"/>
<polygon fill="#000000" stroke="#000000" points="236.4031,-249.3956 226.1411,-246.7607 232.5201,-255.2199 236.4031,-249.3956"/>
</g>
<!-- Y -->
<g id="node13" class="node">
<title>Y</title>
<ellipse fill="none" stroke="#000000" cx="351" cy="-234" rx="27" ry="18"/>
<text text-anchor="middle" x="351" y="-230.3" font-family="Times,serif" font-size="14.00" fill="#000000">Y</text>
</g>
<!-- A&#45;&gt;Y -->
<g id="edge12" class="edge">
<title>A&#45;&gt;Y</title>
<path fill="none" stroke="#000000" d="M323.7146,-288.5708C327.9597,-280.0807 333.1536,-269.6929 337.8663,-260.2674"/>
<polygon fill="#000000" stroke="#000000" points="341.024,-261.7782 342.3657,-251.2687 334.763,-258.6477 341.024,-261.7782"/>
</g>
<!-- C -->
<g id="node3" class="node">
<title>C</title>
<ellipse fill="none" stroke="#000000" cx="99" cy="-162" rx="27" ry="18"/>
<text text-anchor="middle" x="99" y="-158.3" font-family="Times,serif" font-size="14.00" fill="#000000">C</text>
</g>
<!-- X&#45;&gt;C -->
<g id="edge2" class="edge">
<title>X&#45;&gt;C</title>
<path fill="none" stroke="#000000" d="M187.6918,-221.1278C170.6445,-209.763 145.5981,-193.0654 126.4656,-180.3104"/>
<polygon fill="#000000" stroke="#000000" points="128.4031,-177.3956 118.1411,-174.7607 124.5201,-183.2199 128.4031,-177.3956"/>
</g>
<!-- D -->
<g id="node8" class="node">
<title>D</title>
<ellipse fill="none" stroke="#000000" cx="207" cy="-162" rx="27" ry="18"/>
<text text-anchor="middle" x="207" y="-158.3" font-family="Times,serif" font-size="14.00" fill="#000000">D</text>
</g>
<!-- X&#45;&gt;D -->
<g id="edge7" class="edge">
<title>X&#45;&gt;D</title>
<path fill="none" stroke="#000000" d="M207,-215.8314C207,-208.131 207,-198.9743 207,-190.4166"/>
<polygon fill="#000000" stroke="#000000" points="210.5001,-190.4132 207,-180.4133 203.5001,-190.4133 210.5001,-190.4132"/>
</g>
<!-- G -->
<g id="node4" class="node">
<title>G</title>
<ellipse fill="none" stroke="#000000" cx="27" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="27" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">G</text>
</g>
<!-- C&#45;&gt;G -->
<g id="edge3" class="edge">
<title>C&#45;&gt;G</title>
<path fill="none" stroke="#000000" d="M83.7307,-146.7307C73.803,-136.803 60.6847,-123.6847 49.5637,-112.5637"/>
<polygon fill="#000000" stroke="#000000" points="51.7933,-109.8436 42.2473,-105.2473 46.8436,-114.7933 51.7933,-109.8436"/>
</g>
<!-- H -->
<g id="node7" class="node">
<title>H</title>
<ellipse fill="none" stroke="#000000" cx="99" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="99" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">H</text>
</g>
<!-- C&#45;&gt;H -->
<g id="edge6" class="edge">
<title>C&#45;&gt;H</title>
<path fill="none" stroke="#000000" d="M99,-143.8314C99,-136.131 99,-126.9743 99,-118.4166"/>
<polygon fill="#000000" stroke="#000000" points="102.5001,-118.4132 99,-108.4133 95.5001,-118.4133 102.5001,-118.4132"/>
</g>
<!-- M -->
<g id="node5" class="node">
<title>M</title>
<ellipse fill="none" stroke="#000000" cx="27" cy="-18" rx="27" ry="18"/>
<text text-anchor="middle" x="27" y="-14.3" font-family="Times,serif" font-size="14.00" fill="#000000">M</text>
</g>
<!-- G&#45;&gt;M -->
<g id="edge4" class="edge">
<title>G&#45;&gt;M</title>
<path fill="none" stroke="#000000" d="M27,-71.8314C27,-64.131 27,-54.9743 27,-46.4166"/>
<polygon fill="#000000" stroke="#000000" points="30.5001,-46.4132 27,-36.4133 23.5001,-46.4133 30.5001,-46.4132"/>
</g>
<!-- N -->
<g id="node6" class="node">
<title>N</title>
<ellipse fill="none" stroke="#000000" cx="99" cy="-18" rx="27" ry="18"/>
<text text-anchor="middle" x="99" y="-14.3" font-family="Times,serif" font-size="14.00" fill="#000000">N</text>
</g>
<!-- G&#45;&gt;N -->
<g id="edge5" class="edge">
<title>G&#45;&gt;N</title>
<path fill="none" stroke="#000000" d="M42.2693,-74.7307C52.197,-64.803 65.3153,-51.6847 76.4363,-40.5637"/>
<polygon fill="#000000" stroke="#000000" points="79.1564,-42.7933 83.7527,-33.2473 74.2067,-37.8436 79.1564,-42.7933"/>
</g>
<!-- I -->
<g id="node9" class="node">
<title>I</title>
<ellipse fill="none" stroke="#000000" cx="171" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="171" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">I</text>
</g>
<!-- D&#45;&gt;I -->
<g id="edge8" class="edge">
<title>D&#45;&gt;I</title>
<path fill="none" stroke="#000000" d="M198.2854,-144.5708C194.0403,-136.0807 188.8464,-125.6929 184.1337,-116.2674"/>
<polygon fill="#000000" stroke="#000000" points="187.237,-114.6477 179.6343,-107.2687 180.976,-117.7782 187.237,-114.6477"/>
</g>
<!-- J -->
<g id="node12" class="node">
<title>J</title>
<ellipse fill="none" stroke="#000000" cx="243" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="243" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">J</text>
</g>
<!-- D&#45;&gt;J -->
<g id="edge11" class="edge">
<title>D&#45;&gt;J</title>
<path fill="none" stroke="#000000" d="M215.7146,-144.5708C219.9597,-136.0807 225.1536,-125.6929 229.8663,-116.2674"/>
<polygon fill="#000000" stroke="#000000" points="233.024,-117.7782 234.3657,-107.2687 226.763,-114.6477 233.024,-117.7782"/>
</g>
<!-- W -->
<g id="node10" class="node">
<title>W</title>
<ellipse fill="none" stroke="#000000" cx="171" cy="-18" rx="27" ry="18"/>
<text text-anchor="middle" x="171" y="-14.3" font-family="Times,serif" font-size="14.00" fill="#000000">W</text>
</g>
<!-- I&#45;&gt;W -->
<g id="edge9" class="edge">
<title>I&#45;&gt;W</title>
<path fill="none" stroke="#000000" d="M171,-71.8314C171,-64.131 171,-54.9743 171,-46.4166"/>
<polygon fill="#000000" stroke="#000000" points="174.5001,-46.4132 171,-36.4133 167.5001,-46.4133 174.5001,-46.4132"/>
</g>
<!-- Z -->
<g id="node11" class="node">
<title>Z</title>
<ellipse fill="none" stroke="#000000" cx="243" cy="-18" rx="27" ry="18"/>
<text text-anchor="middle" x="243" y="-14.3" font-family="Times,serif" font-size="14.00" fill="#000000">Z</text>
</g>
<!-- I&#45;&gt;Z -->
<g id="edge10" class="edge">
<title>I&#45;&gt;Z</title>
<path fill="none" stroke="#000000" d="M186.2693,-74.7307C196.197,-64.803 209.3153,-51.6847 220.4363,-40.5637"/>
<polygon fill="#000000" stroke="#000000" points="223.1564,-42.7933 227.7527,-33.2473 218.2067,-37.8436 223.1564,-42.7933"/>
</g>
<!-- E -->
<g id="node14" class="node">
<title>E</title>
<ellipse fill="none" stroke="#000000" cx="351" cy="-162" rx="27" ry="18"/>
<text text-anchor="middle" x="351" y="-158.3" font-family="Times,serif" font-size="14.00" fill="#000000">E</text>
</g>
<!-- Y&#45;&gt;E -->
<g id="edge13" class="edge">
<title>Y&#45;&gt;E</title>
<path fill="none" stroke="#000000" d="M351,-215.8314C351,-208.131 351,-198.9743 351,-190.4166"/>
<polygon fill="#000000" stroke="#000000" points="354.5001,-190.4132 351,-180.4133 347.5001,-190.4133 354.5001,-190.4132"/>
</g>
<!-- F -->
<g id="node19" class="node">
<title>F</title>
<ellipse fill="none" stroke="#000000" cx="459" cy="-162" rx="27" ry="18"/>
<text text-anchor="middle" x="459" y="-158.3" font-family="Times,serif" font-size="14.00" fill="#000000">F</text>
</g>
<!-- Y&#45;&gt;F -->
<g id="edge18" class="edge">
<title>Y&#45;&gt;F</title>
<path fill="none" stroke="#000000" d="M370.3082,-221.1278C387.3555,-209.763 412.4019,-193.0654 431.5344,-180.3104"/>
<polygon fill="#000000" stroke="#000000" points="433.4799,-183.2199 439.8589,-174.7607 429.5969,-177.3956 433.4799,-183.2199"/>
</g>
<!-- K -->
<g id="node15" class="node">
<title>K</title>
<ellipse fill="none" stroke="#000000" cx="315" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="315" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">K</text>
</g>
<!-- E&#45;&gt;K -->
<g id="edge14" class="edge">
<title>E&#45;&gt;K</title>
<path fill="none" stroke="#000000" d="M342.2854,-144.5708C338.0403,-136.0807 332.8464,-125.6929 328.1337,-116.2674"/>
<polygon fill="#000000" stroke="#000000" points="331.237,-114.6477 323.6343,-107.2687 324.976,-117.7782 331.237,-114.6477"/>
</g>
<!-- L -->
<g id="node16" class="node">
<title>L</title>
<ellipse fill="none" stroke="#000000" cx="387" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="387" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">L</text>
</g>
<!-- E&#45;&gt;L -->
<g id="edge15" class="edge">
<title>E&#45;&gt;L</title>
<path fill="none" stroke="#000000" d="M359.7146,-144.5708C363.9597,-136.0807 369.1536,-125.6929 373.8663,-116.2674"/>
<polygon fill="#000000" stroke="#000000" points="377.024,-117.7782 378.3657,-107.2687 370.763,-114.6477 377.024,-117.7782"/>
</g>
<!-- O -->
<g id="node17" class="node">
<title>O</title>
<ellipse fill="none" stroke="#000000" cx="315" cy="-18" rx="27" ry="18"/>
<text text-anchor="middle" x="315" y="-14.3" font-family="Times,serif" font-size="14.00" fill="#000000">O</text>
</g>
<!-- K&#45;&gt;O -->
<g id="edge16" class="edge">
<title>K&#45;&gt;O</title>
<path fill="none" stroke="#000000" d="M315,-71.8314C315,-64.131 315,-54.9743 315,-46.4166"/>
<polygon fill="#000000" stroke="#000000" points="318.5001,-46.4132 315,-36.4133 311.5001,-46.4133 318.5001,-46.4132"/>
</g>
<!-- P -->
<g id="node18" class="node">
<title>P</title>
<ellipse fill="none" stroke="#000000" cx="387" cy="-18" rx="27" ry="18"/>
<text text-anchor="middle" x="387" y="-14.3" font-family="Times,serif" font-size="14.00" fill="#000000">P</text>
</g>
<!-- K&#45;&gt;P -->
<g id="edge17" class="edge">
<title>K&#45;&gt;P</title>
<path fill="none" stroke="#000000" d="M330.2693,-74.7307C340.197,-64.803 353.3153,-51.6847 364.4363,-40.5637"/>
<polygon fill="#000000" stroke="#000000" points="367.1564,-42.7933 371.7527,-33.2473 362.2067,-37.8436 367.1564,-42.7933"/>
</g>
<!-- S -->
<g id="node20" class="node">
<title>S</title>
<ellipse fill="none" stroke="#000000" cx="459" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="459" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">S</text>
</g>
<!-- F&#45;&gt;S -->
<g id="edge19" class="edge">
<title>F&#45;&gt;S</title>
<path fill="none" stroke="#000000" d="M459,-143.8314C459,-136.131 459,-126.9743 459,-118.4166"/>
<polygon fill="#000000" stroke="#000000" points="462.5001,-118.4132 459,-108.4133 455.5001,-118.4133 462.5001,-118.4132"/>
</g>
<!-- T -->
<g id="node21" class="node">
<title>T</title>
<ellipse fill="none" stroke="#000000" cx="531" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="531" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">T</text>
</g>
<!-- F&#45;&gt;T -->
<g id="edge20" class="edge">
<title>F&#45;&gt;T</title>
<path fill="none" stroke="#000000" d="M474.2693,-146.7307C484.197,-136.803 497.3153,-123.6847 508.4363,-112.5637"/>
<polygon fill="#000000" stroke="#000000" points="511.1564,-114.7933 515.7527,-105.2473 506.2067,-109.8436 511.1564,-114.7933"/>
</g>
<!-- U -->
<g id="node22" class="node">
<title>U</title>
<ellipse fill="none" stroke="#000000" cx="495" cy="-18" rx="27" ry="18"/>
<text text-anchor="middle" x="495" y="-14.3" font-family="Times,serif" font-size="14.00" fill="#000000">U</text>
</g>
<!-- T&#45;&gt;U -->
<g id="edge21" class="edge">
<title>T&#45;&gt;U</title>
<path fill="none" stroke="#000000" d="M522.2854,-72.5708C518.0403,-64.0807 512.8464,-53.6929 508.1337,-44.2674"/>
<polygon fill="#000000" stroke="#000000" points="511.237,-42.6477 503.6343,-35.2687 504.976,-45.7782 511.237,-42.6477"/>
</g>
<!-- V -->
<g id="node23" class="node">
<title>V</title>
<ellipse fill="none" stroke="#000000" cx="567" cy="-18" rx="27" ry="18"/>
<text text-anchor="middle" x="567" y="-14.3" font-family="Times,serif" font-size="14.00" fill="#000000">V</text>
</g>
<!-- T&#45;&gt;V -->
<g id="edge22" class="edge">
<title>T&#45;&gt;V</title>
<path fill="none" stroke="#000000" d="M539.7146,-72.5708C543.9597,-64.0807 549.1536,-53.6929 553.8663,-44.2674"/>
<polygon fill="#000000" stroke="#000000" points="557.024,-45.7782 558.3657,-35.2687 550.763,-42.6477 557.024,-45.7782"/>
</g>
</g>
</svg>