Recursion performance in Monkey?

Monkey Forums/Monkey Beginners/Recursion performance in Monkey?

Aman(Posted 2014) [#1]
Does Monkey use Tail call optimization or does it suffer from allocating a new stack frame for every call?

I am just trying to figure out the most efficient way to handle iteration.


maltic(Posted 2014) [#2]
It depends on the target language. Typical TCO requires runtime support, and Monkey has no 'runtime'. Monkey could, of course, convert tail recursive functions into loops, but there are problems with mutual recursion.

What do you mean by efficient? TCO is a space optimization, not a speed one. If you are running out of space, you could always convert your recursion to a loop by hand.

Off the top of my head:
C++ doesn't guarantee TCO, but may apply it. Javascript generally doesn't have TCO, but I believe V8 does, and the new spec calls for proper tail calls (I think, not a Javascript buff). I don't think Flash does. Java definitely does not. I believe C# (XNA) does have TCO.


Gerry Quinn(Posted 2014) [#3]
TCO is basically a functional language thing IMO, because in those you are using recursion all the time. Monkey and its targets are imperative languages which mostly only use recursion when they actually want to recurse, so I would not expect any special optimisations. You should probably avoid deep recursion for flood-filling and such in these languages, and unroll by hand.

Lack of threading can be an issue too - if you're doing a chess game or similar in Monkey you'll probably want to make your own stack so you can come out of a long analysis a few times per second to update the screen.


Aman(Posted 2014) [#4]
Thanks. I got used to do stuff recursively I noticed some problems on some targets but not all. Looks like I am going to start avoiding recursion.Time to rewrite a good chunk of my code.


Midimaster(Posted 2014) [#5]
I got big problems when tryed to do flood-fill. So I also had to replace my recursive algos with iterative algos on the java target.


Gerry Quinn(Posted 2014) [#6]
You don't have to be scared of using recursion, just very deep recursion.