Recamán's sequence - Recursive LAMBDA vs. REDUCE

[Patrick2788]

I've been studying recursion by taking on some of the well known integer sequences.  This post examines two solutions for creating Recamán's sequence.

Recamán's sequence - Wikipedia

A005132 - OEIS

Recamán's sequence: The Rules

• Start at 0 (Element position also begins at 0) and avoid 0 after the start.
• Avoid negatives
• Subtract whenever possible, otherwise add
• Subtraction: Previous Element - Current Element Position
• Addition: Previous Element + Current Element Position
• If the results of Subtraction would mean adding a number that's already appeared in the list, Add.
• If the results of Subtraction and Addition would be adding a repeat, Subtract.
• There will be some repeats but the above rules mimimize them

Example

Element	a(n)
0	0	Start at Zero
1	1	The result of subtraction would be be -1 (0 - 1), so we add
2	3	The result of subtraction would be be -1 (1 - 2), so we add
3	6	The result of subtraction would be 0 (3-3), so we add
4	2	The result of subtraction is 2 (6-4) and not already in list

The Recursive Solution

'Recamán
=LAMBDA(a,v,IF(
    n = 1,
    start,
    Recamán(
        LET(
            r, ROWS(start),
            v, TAKE(start, -1),
            subtract, v - r,
            add, v + r,
            arith, IF(
                v = 0,
                1,
                IF(AND(subtract > 0, ISERROR(XMATCH(subtract, start))), subtract, add)
            ),
            VSTACK(start, arith)
        ),
        n - 1
    )
))

The REDUCE solution

'GenArray
=LAMBDA(a,v,LET(
    subtract, TAKE(a, -1) - v,
    add, TAKE(a, -1) + v,
    outcome, IF(AND(subtract > 0, ISERROR(XMATCH(subtract, a))), subtract, add),
    VSTACK(a, outcome)
))

'RecamánR
=LAMBDA(n,REDUCE(, SEQUENCE(n, , 0), GenArray))

The Results

Discussion

I'm interested in the recursive approach despite the limitations. I'm also interested in a Lambda/helper solution that's more efficient than the above approach with REDUCE.

[#2]

@Patrick2788 I don't have an answer, just to comment. It is a very elegant solution, I was reviewing the REDUCE approach, and how you simplified the following:

Recaman=LAMBDA(n,REDUCE(, SEQUENCE(n,,0), 
 LAMBDA(ac, a, GenArray(ac,a))));

replacing the second LAMBDA with the the function name. As you mentioned it is not efficient. I was thinking to use XMATCH with binary search, but the sequence is not sorted. I have seen with other similar applications of REDUCE/VSTACK pattern the same lack of performance. I would say something for Microsoft to improve. I added this feedback, in case you want to vote: Improve performance of REDUCE/VSTACK or REDUCE/HSTACK. 

The Racaman sequence hasn't been studied too much compared to Fibonacci, so I could not find any indirect calculation that would avoid recursion or iteration. 

[#3]

@davidleal Thank you for the reply. I voted for your feedback and left a comment.

re: calculation performance -  I've been looking for some technical documentation on Lambda helper functions for a while. I'd like a resource that's much more in depth than the standard support page for functions.  I'm interested in how the functions calculate so I can pick the best ones for the situation.

re: efficiency

I'm attaching a sample to this post where OFFSET proves to be a better option than TAKE in creating dynamic ranges for a tree map chart.  It was a situation where the data could not be tabled.