Lambda Example: Generate Fibonacci series

nfib_v1 = LAMBDA(n, IF(n <= 2, 1, nfib_v1(n - 1) + nfib_v1(n - 2)))

If found the following approach to avoid recursion (formula 2)

nfib_v2 = LAMBDA(n,REDUCE({1;1},SEQUENCE(IF(n<=2,1,n-2)), 
LAMBDA(ac,a, IF(n<=2,1,LET(x_1,TAKE(ac,1),x_2,DROP(ac,1), 
IF(a=(n-2),x_1+x_2, VSTACK(x_2, x_1+x_2)))))))

 Taking into consideration the performance:

• formula 1 for 30 Fibonacci numbers takes 1800ms. Around 50 Fibonacci number start crashing
• formula 2 for 30 Fibonacci numbers returns the result instantaneously. My Excel reports 0ms. It starts showing some time consuming around 1000 Fibonacci numbers, consuming 20ms. 

So the recursive approach is an elegant approach, but not a good one in terms of performance.

Back to the original problem generating a sequence of Fibonacci numbers is straightforward using formula 2 (formula 3):

nfibo_serie = LAMBDA(m, MAP(SEQUENCE(m), LAMBDA(x, nfib_v2(x))))

The good news about this approach is that you can generate any sequence of numbers (x), with a simple modification:

nfibo_serie = LAMBDA(x, MAP(x, LAMBDA(n, nfib_v2(n))))

The bad news is the performance, compared to the elegant solution provided by: lori_m : (formula 4)

FIBO_SERIE.v0 = LAMBDA(n,IF(n<=2,SEQUENCE(n,,1,0), 
LET(b,FIBO_SERIE.v0(n-1), IF(SEQUENCE(n)<n,b,
 INDEX(b,n-1) + INDEX(b,n-2)))))

Note: I just adapted the solution to start from F1=1. 

Here are the performance results for n=1000

• Formula 3: nfibo_serie(1000): 1,230ms
• Formula 4: FIBO_SERIE.v0(1000): 110ms

as you can see it is a huge difference, I would suspect the main reason is MAP call (I also tested it with BYROW a little bit faster, but nothing relevant). and under this approach, I don't see a way to get rid of MAP. 

So as you can see we have several situations where the recursive approach has been significantly time-consuming, but not for this case.

To understand how the recursion works for this case (Formula 4) provided by lori_m.  We can see how it works for the case of 5. From the formula as you can see the recursion ends when n=2, so for this case what it does is the following process:

In column, A you have the final result, but the recursion goes back up to the n=2 (column D), so you should read it from column D (n=2) to column C (n=3), etc. so the formula does this backward calculation until the entire recursion is expanded up to the end n=2. On each call of the recursion, only the last row changes from the previous one, adding the next Fibonacci number. It is ensured by the second IF condition until it goes to the last one which is the sequence: {1;1}.

I hope this graphical representation helps to understand the formula.

UPDATE

Later I found that we can use an indirect way to obtain the Fibonacci number using the following mathematical formulation based on the Binet formula:

F(n) = (phi^n - (1-phi)^n) / sqrt(5)

where phi is the golden ratio: 1.618, so in Excel it can be formulated as follows using the simplified Binet formula (check the link):

=LAMBDA(n,ROUND(POWER((1+SQRT(5))/2,n)/SQRT(5),0))

I verified this formula has the fastest performance among all the formulas on this post. Using this formula, you can now generate the sequence as follows:

FIBO_SERIE=LAMBDA(x, BYROW(x, LAMBDA(n, FIBO(n))));

Here is the performance result for the first 1000 Fibonacci numbers:

• FIBO_SERIE.v0(1000): Around 100ms
• FIBO_SERIE(SEQUENCE(1000)): less than 20ms

So, the last FIBO_SERIE formula is not just very short, but the fastest solution among others.

NOTE: there is no need to create an additional LAMBDA function, since all the functions involved in FIBO work with arrays, i.e.:

FIBO(SEQUENCE(1000))

which should be even faster than FIBO_SERIE which uses BYROW. I tested it for the first 10K Fibonacci numbers and almost instantaneously, the worst try was 20ms.