Forum Discussion
Recamán's sequence - Recursive LAMBDA vs. REDUCE
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
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.
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.
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.
