RECURSION statement clarification

[hernad]

I am struggling with lsfusion documentation (I have using auto translation from russian to english, as I don't understand russian).

First, fibonacci given example don't work. When I put this in my playground project:

fib(i) = RECURSION 1 IF (i==0 OR i==1) 
   STEP 1 IF (i==$i+1 OR i==$i+2);

platform generates exceptions because of integer limits. I have fixed it putting limit on i < 60, and using LONG (bigint):

fib(i) = RECURSION 1l IF (i==0 OR i==1) 
   STEP 1l IF (i=$i+1 OR i=$i+2)
   AND i < 60;

Again, fibanocci function is not calculated like we want. We had to add i>1 to make fib(1)=1. Without that condition the result is fib(1)=2.

fib(i) = RECURSION 1l IF (i = 0 OR i = 1) 
            STEP 1l IF (i = $i + 1 OR i = $i + 2 OR i = $i + 3) AND i > 1 AND i < 60
            CYCLES IMPOSSIBLE; 

Anyway, the most problematic part for me was understanding how this works at all!?

STEP 1l IF (i = $i + 1 OR i = $i + 2)

At the end, This is my understanding:
In next evaluation step the result is previous value i = $i + 1 plus OR second previous value i = $i + 2.
The result is multiplied by 1.

So, If we put this:

fib3(i) = RECURSION 1l IF (i = 0 OR i = 1) 
    STEP 3l IF (i = $i + 1 OR i = $i + 2 OR i = $i + 3) AND i > 1 AND i < 60
    CYCLES IMPOSSIBLE; 

we are going to get result as fib3(i) = 3 * ( fib3(i-1) + fib3(i-2) + fib3(i-3)):

fib3(0)=1
fib3(1)=1
fib3(2)=(1+1+null)*3=6
fib3(3)=(6+1+1)*3=24
fib3(4)=93 

...etc...

I am aware that this example has no practical usage. It is written this for the sake of understanding how the RECURSION statement makes the calculation.

[hernad]

I have to add that expression after STEP doesn't look intuitive to me at all.

Instead i = $i + 1 OR i = $i + 2, it would be more understandable to me something like this i = $(i+1) + $(i+2).
Even better: i = $(i-1) + $(i-2)

[danchanka]

I am struggling with lsfusion documentation (I have using auto translation from russian to english, as I don't understand russian).

We have documentation in English. The process of thanslation is not finished yet, but you might find it useful.

[hernad]

Thank's @danchanka. I have managed on my own. If someone needs it, I have collected these materials till now:

• English documentation, scrapped and translated from documentation lsfusion
• Article on habr.com

[AlexKirkouski]

First of all, You can use https://en-documentation.lsfusion.org to get english version for now. Now only article captions and comments in examples are not translated, but it will be done soon (and then documentation.lsfusion.org will be in english by default).

Regarding your main question, the thing is that, basically RECURSION is more like breadth-first search than depth-first search. So $X is the reference to a parameter rather than the reference to a function value (previous function value is used implicitly - multiplied with the step value and added to the final result). That's why it is not that evident, when RECURSION operator is used for working with recursive functions (and even trees) and might be a quite confusing. To understand how this operator works it's better to read how recursive CTEs work in SQL, and this operator works the same way (and sometimes uses them) except that it uses functions instead of tables (actually that's one of the main features of lsFusion, in a way, it's a sort of "functional SQL").

In case of fibonacci numbers, it works like, we start with values
0 1 - 1 (initial iteration)
1 2 2 3 - 1 (previous iteration result) * 1 (step)
2 3 3 4 3 4 4 5 - 1 (previous iteration result) * 1 (step)
3 4 4 5 4 5 ....

(actually all the same keys are grouped on each iteration and sumed up, that's by the way why SQL RECURSIVE CTEs usually cannot be used - they don't support grouping, so generated table functions + temporary tables are used instead)

final result
0 - 1
1 = 1 + 1 = 2
2 = 1 + 1 + 1 = 3
3 = 1 + 1 + 1 + 1 + 1 = 5

.....

So it's not easy to understand / to prove that the result of such calculation is "fibonacci numbers", but it is.

RECURSION operator is implemented / defined this way not only because this implementation / definition is compliant with SQL (and thus has a lot more efficient calculation), but because this implementation / definition has a very efficient incremental update mechanism (not worse than GROUP SUM).

But nevertheless RECURSION is one of the most complicated operators in lsFusion, and usually is used for pretty basic cases described in samples (i.e. calculating tree depth / reachability, number of pathes in graph and so on).

[hernad]

Ok. There is bug with fibonacci in my earlier writing. fib(0) is not 1, it has to be fib(0)=0 . The only way to do that with lsfusion, as far as I know is this:

fibR(i) = RECURSION 1l IF (i == 1) 
            STEP 1l IF (i = $i + 1 OR i = $i + 2) AND i > 0 AND i < 30
            CYCLES IMPOSSIBLE;            
    
fib(i) = IF i == 0 THEN 0 ELSE fibR(i);

action to show fib(0) - fib(10):

showMessage() {

    LOCAL i = INTEGER();
    i() <- 0;
    
    WHILE i() < 11 DO {
        MESSAGE 'fib(' + i() + ')=' + (fib(i()));
        i() <- i() + 1;
    }
   
}

This is something I would like to see in the documentation :). Something what I can easily run.

[hernad]

To understand how this operator works it's better to read how recursive CTEs work in SQL ..

CTEs - recursive common table expressions

https://www.postgresqltutorial.com/postgresql-recursive-query/

[hernad]

Excerpt from lsfusion documentation:

Currently, only two types of aggregate functions are supported for the recursion operator - SUM and OR . The latter is used when the initial value and step are of the class BOOLEAN. SUM is used in all other cases.
Note that at some iteration, sets of objects may start repeating. In this case, we will say that a cycle is formed. There are three policies for working with cycles:

1. CYCLES YES - cycles are allowed. In this case, when a loop is detected, the property value will equal the maximum allowed value for the value class of this property. This policy is not supported when the initial value and step are BOOLEAN .
2. CYCLES NO (default) - no cycles are allowed. It works similarly to the previous policy, but in addition, a restriction is created that the value of the obtained property should not be equal to the maximum value (which just means that a cycle has formed for a given set of objects).
3. CYCLES IMPOSSIBLE - no cycles possible. As a rule, it is used if there is some counter among the objects, which increases at each iteration and, as a result, cannot be repeated.

I would be useful to explain CYCLES option with three characteristic examples.

[AlexKirkouski]

Regarding the example, there is an another way to fix first values in fibonacci function. Plus there is a more appropriate way to output results. You can put this code in https://lsfusion.org/try (RDBMS mode) to see results:

fib(i, to) = RECURSION 1 IF (i==0 OR i==1) AND to IS INTEGER STEP 1 IF (i==$i+1 OR i==$i+2) AND i<=to CYCLES IMPOSSIBLE;

FORM showFib
     OBJECTS to = INTEGER PANEL, i=INTEGER
     PROPERTIES value = (OVERRIDE fib(i-2, to), 1)
     FILTERS iterate(i, 1, to);
;

run() {
     EXPORT showFib OBJECTS to=20;
}

Or you can try this in any demo, in Administration -> Interpreter. Button Run script.

fib(i, to) = RECURSION 1 IF (i==0 OR i==1) AND to IS INTEGER STEP 1 IF (i==$i+1 OR i==$i+2) AND i<=to CYCLES IMPOSSIBLE;

FORM showFib
     OBJECTS to = INTEGER PANEL, i=INTEGER
     PROPERTIES i = i AS INTEGER, fib = (OVERRIDE fib(i-2, to), 1)
     FILTERS iterate(i, 1, to);
;

run() {
     SHOW showFib OBJECTS to=20;
}

[hernad]

Alex, thank you for the tips! Running examples like this this is really extremely useful and powerful :).
But your example doesn't work as expected: fib(0)=0, fib(1)=1, fib(2) = fib(0)+fib(1), fib(3) = fib(2)+fib(1) ...

This works like it should:

fibR(i, to) = RECURSION 1 IF (i == 1)  AND to IS INTEGER STEP 1 IF (i = $i + 1 OR i = $i + 2) AND i > 0  AND i <= to CYCLES IMPOSSIBLE;            
    
fib(i, to) = IF (i == 0) THEN 0 ELSE fibR(i, to);

funCall(i) = 'fib(' + i + ')';

FORM showFib
     OBJECTS to = INTEGER PANEL, i=INTEGER
     PROPERTIES i 'call' = funCall(i) AS STRING[10], fib 'Result' = fib(i, to)
     FILTERS iterate(i, 0, to)
;

run() {
     SHOW showFib OBJECTS to=20;
}