Recursive vs. iterative SCL code

There are two approaches to solving a problem in computing that requires visiting a lot of states. Iterative and recursive. The iterative approach involves loops and is usually more memory efficient. The recursive approach involves code that calls itself over and over again and is usually more memory demanding. Then why do we need recursion on the first place? Well … most of the terms that we deal with in our lives are recursive by definition. (examples: natural numbers, factorials, Fibonacci numbers, fractals, grammar rules etc. ) The recursive approach provides a natural and simple way to express such concepts in the code. SCL scripting is not any different. You can easily do a script that calls itself. What you should be aware is that within your code you need to ensure a termination condition for the recursion to stop. Failing to do so will eventually eat up the whole stack and the code will crash.

To demo the two concepts I am implementing a recursive and an iterative version of a function that calculates factorials.

Here is how the recursive version looks:

FUNCTION "FACTORIAL" : DINT
VERSION:1.0
VAR_INPUT
	n:DINT;
END_VAR
BEGIN
    IF #n = 0 THEN // terminating condition
		#FACTORIAL := 1;
	ELSE
		#FACTORIAL := #n * "FACTORIAL"(#n - 1);
	END_IF;
END_FUNCTION  

Pretty simple isn't it? Just like the definition:

In your main script you call the function like any other function:

 #out := "FACTORIAL"(5);

The one thing you should be careful about is what value you pass on input. If you pass a number that is too large (let's say 1000) this will make the recursion too deep and probably will consume the thread's stack. In other words it is very likely for Process Simulate to crash.

So the recommendation is: make sure the recursion is shallow if you use it

I cannot give exact recommendation about the depth. It all depends on the space left on the stack before the recursion begins. The one thing that is sure is that the SCL code consumes quite a lot of space on the stack since it internally iterates the program tree. The more complex (nested) the code is, the more space it consumes on the stack.

A better way to implement this function is to use the iterative approach like this:

FUNCTION "FACTORIAL2" : DINT
VERSION:1.0
VAR_INPUT
	n:DINT;
END_VAR
VAR_TEMP
	i:DINT;
END_VAR
BEGIN
	#FACTORIAL2 := 1;
	FOR #i := 1 TO #n DO
		#FACTORIAL2 := #FACTORIAL2 * #i;
	END_FOR;
END_FUNCTION

It behaves the same way but does not have the memory limitations of the first one. It is also a lot faster (linear complexity). The recursive version is also linear but the price for the function calls is quite high.

Sometimes it can be very easy to come up with a recursive version and very hard to do the iterative one. In those cases I usually prefer to do the recursion despite the pitfalls.

At the end it is up to you to decide.

See you in the next one!