# How can I reverse this recursive function?

This is the python code I wrote of a simple crackme that I have reversed but I am not able to understand what the recursive function here does.

```def the_process(stored, inp, size):
idx = 0
global thstr
idx = stored.index(inp[0])
if idx:
the_process(stored[:idx], inp[1:], idx)
if size - 1 != idx:
the_process(stored[1+idx:1+idx + size - idx -1],inp[idx+1:], size - idx - 1)
thstr.append(inp[0])

if __name__ == "__main__":
thstr = []
stored = "MGNCHXWIZDJAOKPELYSFUTV"
input1 = "TFSLPOJZCGMNHWXIDAKEYUV"
the_process(stored, list(input1), 23)
print "output : " + "".join(thstr)
```

`input1` is a sample valid input I could figure out for the function. To get the crackme validated I need `thstr` to be `MNGHCWZIJDXOPKLESUVTFYA` in the end. How can I get the input to make that happen?

I gave it a go. First I simplified your code a little bit.

``````def the_process(stored, inp, size):
global thstr
idx = 0
idx = stored.index(inp[0])
if idx:
the_process(stored[:idx], inp[1:], idx)
if size - 1 != idx:
the_process(stored[idx+1:],inp[idx+1:], size - idx - 1)
thstr.append(inp[0])
``````

Now it looks like by the naming that `stored` is hardcoded in the binary. I considered `MGNCHXWIZDJAOKPELYSFUTV` to be as is and the target output to be `MNGHCWZIJDXOPKLESUVTFYA`.

By the function it looks like that it takes the first char of `input`, splits `stored` at the location of that char and then recursively calls itself on the two parts made. I made a tree to follow that.

The graph is such that taking one char from input `TFSLPOJZCGMNHWXIDAKEYUV` and position nodes/chars which are at the right/left appropriately(V is right to T in the graph as it is right to T in the `stored`). In this graph the output is post order traversal of the graph and the input is pre order traversal.

Similar graph can be constructed from the `target` `MNGHCWZIJDXOPKLESUVTFYA`. Only the reverse such that post order is given and construct the graph.

Now pre order traverse this graph and you'll have your input `AXCGMNHDIWZJYEKOPLFSTUV`.

The equivalent hackish function is this. feel free to make it better.

``````def rev_process(stored, 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)
``````

I have also added the reversed function code and resources here

• I think I was not able to explain it fully. Comment your queries and I'll try to help. – sudhackar Sep 7 '18 at 10:35
• What software you used for the tree drawing? – MiniMax Apr 7 at 18:25
• I used `dot` from the `graphviz` package. The dot files are here – sudhackar Apr 8 at 8:02

you say you wrote it and you can understand what you wrote ??

have you tried debugging it or stepping through the code

``````C:\>python -m pdb foo.py
> c:\foo.py(1)<module>()
-> def the_process(stored, inp, size):
(Pdb) s
> c:\foo.py(11)<module>()
-> if __name__ == "__main__":
(Pdb) s
> c:\foo.py(12)<module>()
-> thstr = []
(Pdb) s
> c:\foo.py(13)<module>()
-> stored = "MGNCHXWIZDJAOKPELYSFUTV"
(Pdb) s
> c:\foo.py(14)<module>()
-> input1 = "TFSLPOJZCGMNHWXIDAKEYUV"
(Pdb) s
> c:\foo.py(15)<module>()
-> the_process(stored, list(input1), 23)
(Pdb) p strored
*** NameError: NameError("name 'strored' is not defined",)
(Pdb) p stored
'MGNCHXWIZDJAOKPELYSFUTV'
(Pdb) p list(input1)
['T', 'F', 'S', 'L', 'P', 'O', 'J', 'Z', 'C', 'G', 'M', 'N', 'H', 'W', 'X', 'I', 'D', 'A', 'K', 'E', 'Y', 'U', 'V']
(Pdb) p size
*** NameError: NameError("name 'size' is not defined",)
(Pdb) s
--Call--
> c:\foo.py(1)the_process()
-> def the_process(stored, inp, size):
(Pdb) p size
23
(Pdb) p inp
['T', 'F', 'S', 'L', 'P', 'O', 'J', 'Z', 'C', 'G', 'M', 'N', 'H', 'W', 'X', 'I', 'D', 'A', 'K', 'E', 'Y', 'U', 'V']
(Pdb) p stored
'MGNCHXWIZDJAOKPELYSFUTV'
(Pdb) p thstr
[]
(Pdb) s
> c:\foo.py(2)the_process()
-> idx = 0
(Pdb) s
> c:\foo.py(4)the_process()
-> idx = stored.index(inp[0])
(Pdb) s
> c:\foo.py(5)the_process()
-> if idx:
(Pdb) p idx
21
(Pdb) p inp
['T', 'F', 'S', 'L', 'P', 'O', 'J', 'Z', 'C', 'G', 'M', 'N', 'H', 'W', 'X', 'I', 'D', 'A', 'K', 'E', 'Y', 'U', 'V']
(Pdb) p inp[0]
'T'
(Pdb) ?

Documented commands (type help <topic>):
========================================
EOF    bt         cont      enable  jump  pp       run      unt
a      c          continue  exit    l     q        s        until
alias  cl         d         h       list  quit     step     up
args   clear      debug     help    n     r        tbreak   w
b      commands   disable   ignore  next  restart  u        whatis
break  condition  down      j       p     return   unalias  where

Miscellaneous help topics:
==========================
exec  pdb

Undocumented commands:
======================
retval  rv

(Pdb) rv
*** Not yet returned!
(Pdb) retval
*** Not yet returned!
(Pdb) bt
c:\python27\lib\bdb.py(400)run()
-> exec cmd in globals, locals
<string>(1)<module>()
c:\foo.py(15)<module>()
-> the_process(stored, list(input1), 23)
> c:\foo.py(5)the_process()
-> if idx:
(Pdb) pp
*** SyntaxError: SyntaxError('unexpected EOF while parsing', ('<string>', 0, 0, ''))
(Pdb) a
stored = MGNCHXWIZDJAOKPELYSFUTV
inp = ['T', 'F', 'S', 'L', 'P', 'O', 'J', 'Z', 'C', 'G', 'M', 'N', 'H', 'W', 'X', 'I', 'D', 'A', 'K', 'E', 'Y', 'U', 'V'
]
size = 23
(Pdb) l
1     def the_process(stored, inp, size):
2         idx = 0
3         global thstr
4         idx = stored.index(inp[0])
5  ->     if idx:
6             the_process(stored[:idx], inp[1:], idx)
7         if size - 1 != idx:
8             the_process(stored[1+idx:1+idx + size - idx -1],inp[idx+1:], size - idx - 1)
9         thstr.append(inp[0])
10
11     if __name__ == "__main__":
(Pdb)
``````
• maybe he translated from asm/c to python not actually understood the application flow. – sudhackar Aug 1 '18 at 5:58