Recursive vs loops

[Infinitegde]

I know in most languages and in general, loops are must more efficient than recursive. Is that right in ALL cases in jass/vJass?

 

[PurgeandFire]

Yes, that should be correct in all cases. (looping > recursive calls)

 

[Sevion]

Looping is faster because the recursive call requires you to make a function call (duh) and that's simply just slower than the time it takes to loop.

 

[tooltiperror]

Recursion has benefits, however. Namely getting past function operation limits.

 

[Narks]

Recursion doesn't start new threads? How can recursion bypass the op limit?

 

[Infinitegde]

what are the function operation limits o.o?!

 

[tooltiperror]

function foo
    local integer x=0
    loop
        set x=x+1
        call BJDebugMsg(I2S(x*2+1))
    endloop
endfunction

//=========================================

globals
    integer x
endglobals

function bar takes nothing returns nothing
    set x=x+1
    call BJDebugMsg(I2S(x))
    call ExecuteFunc("bar")
endfunction

The loop will end eventually, the recursion won't?

 

[Sevion]

You're wrong tooltiperror. The recursive function will hit the op limit and crash the thread because it doesn't start new threads.

In any situation with JASS you should use a loop or timer.

 

[PurgeandFire]

I think Narks meant if you just use [ljass]call bar()[/ljass]. That would hit the op limit eventually. If you use ExecuteFunc(), then yeah, it won't crash, but it will definitely be a lot slower. xD

>what are the function operation limits o.o?!

It depends on the functions called. Just stay away from massive codes all ran on the same thread. (you'll probably encounter this when dealing with strings/save codes)

 

[Nestharus]

I know in most languages and in general, loops are must more efficient than recursive. Is that right in ALL cases in jass/vJass?

Actually, recursive loops are generally faster than plain loops in most languages.

Here is a more general answer ripped from Yahoo Answers =).

This depends on the language being used. You wrote 'language-agnostic', so I'll give some examples.

In Java, C, and Python, recursion is fairly expensive compared to iteration (in general) because it requires the allocation of a new stack frame. In some C compilers, one can use a compiler flag to eliminate this overhead, which transforms certain types of recursion (actually, certain types of tail calls) into jumps instead of function calls.

In functional programming language implementations, sometimes, iteration can be very expensive and recursion can be very cheap. In many, recursion is transformed into a simple jump, but changing the loop variable (which is mutable) sometimes requires some relatively heavy operations, especially on implementations which support multiple threads of execution. Mutation is expensive in some of these environments because of the interaction between the mutator and the garbage collector, if both might be running at the same time.

I know that in some Scheme implementations, recursion will generally be faster than looping.

In short, the answer depends on the code and the implementation. Use whatever style you prefer. If you're using a functional language, recursion might be faster. If you're using an imperative language, iteration is probably faster. In some environments, both methods will result in the same assembly being generated (put that in your pipe and smoke it).

Addendum: In some environments, the best alternative is neither recursion nor iteration but instead higher order functions. These include "map", "filter", and "reduce" (which is also called "fold"). Not only are these the preferred style, not only are they often cleaner, but in some environments these functions are the first (or only) to get a boost from automatic parallelization — so they can be significantly faster than either iteration or recursion. Data Parallel Haskell is an example of such an environment.

List comprehensions are another alternative, but these are usually just syntactic sugar for iteration, recursion, or higher order functions.

Keep in mind that wc3 op limit is based on memory. If recursive loops take up way more memory, then that means that you will not be able to do as many iterations in a recursive loop as you could in a regular loop for wc3.

Also, keep in mind that arguments in wc3 are strings (parsed into the actual values). This is why calling a function of several parameters has such a massive overhead. In wc3, I'm pretty positive that a function with 1 parameter is going to be much slower for recursion than looping through an array just because of the parsing involved with interpreting the arguments. I'm unsure of a function with no parameters.

Really, it doesn't matter all too much... because it's JASS, I don't recommend recursive loops ;P.

 

[Solmyr]

Keep in mind that wc3 op limit is based on memory.

I've no idea what you're talking about.

In WC3, each instance of the virtual machine (new one on event, [ljass]TriggerExecute()[/ljass], [ljass]TriggerEvaluate()[/ljass], [ljass]ExecuteFunc()[/ljass] and [ljass]TriggerSleepAction()[/ljass]) has a limit of 300000 operation at continuous execution, at which point the VM returns.

And yes, if you read my post well, you will see that you can use [ljass]TriggerSleepAction()[/ljass] to avoid hitting the op-limit, as it puts the thread on sleep and resets the op-count upon picking it back up.

You can use Grimoire with war3err to dump bytecode as it's being executed.

Here's a list that should contain most (if not all) of the operations:

enum OPCODES { OP_ENDPROGRAM=0x1,
	OP_FUNCTION=0x3, // _ _ rettype funcname
	OP_ENDFUNCTION=0x4,
	OP_LOCAL=0x5, // _ _ type name
	OP_GLOBAL=0x6,OP_CONSTANT=0x7,
	OP_POPFUNCARG=0x8, // _ srcargi type destvar
	OP_CLEANSTACK=0xB, // _ _ nargs _
	OP_LITERAL=0xC, // _ type destreg srcvalue
	OP_SETRET=0xD, // _ srcreg _ _
	OP_GETVAR=0xE, // _ type destreg srcvar
	OP_CODE=0xF,
	OP_GETARRAY=0x10,
	OP_SETVAR=0x11,	// _ _ srcreg destvar
	OP_SETARRAY=0x12,
	OP_PUSH=0x13, // _ _ srcreg _
	OP_SETRIGHT=0x14,
	OP_NATIVE=0x15, // _ _ _ fn
	OP_JASSCALL=0x16, // _ _ _ fn
	OP_I2R=0x17,
	OP_AND = 0x18,
	OP_OR = 0x19,
	OP_EQUAL=0x1A,
	OP_NOTEQUAL=0x1B,		// check
	OP_LESSEREQUAL=0x1C,OP_GREATEREQUAL=0x1D,
	OP_LESSER=0x1E,OP_GREATER=0x1F,
	OP_ADD=0x20,OP_SUB,OP_MUL,OP_DIV,
	OP_MODULO = 0x24,              // unused
	OP_NEGATE=0x25,
	OP_NOT = 0x26,
	OP_RETURN=0x27,	// _ _ _ _
	OP_JUMPTARGET=0x28,
	OP_JUMPIFTRUE=0x29,OP_JUMPIFFALSE=0x2A,
	OP_JUMP=0x2B
}

 

[Nestharus]

woops, my bad on the memory portion.