Lambda Example: Generate Fibonacci series

I realize this solution is not the most efficient but it was fun to create and it's a bit different (Inspired by Pascal's Triangle).

'DiagonalSum
=LAMBDA(a,v,VSTACK(
    a,
    IF(v < 3, 1, SUM(IFERROR(COMBIN(SEQUENCE(v - 1, , v - 1, -1), SEQUENCE(v - 1, , 0)), 0)))
))

'Fib
=LAMBDA(elements,REDUCE(0, SEQUENCE(elements), DiagonalSum))

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.

Viz et al

Thanks for this discussion.  It has been useful in taking me from the point where I didn't know there was a limit on the level of recursion achievable to actually acquiring some understanding of the factors involved.

tboulden 

I am pleased the exchange of workbooks has delivered an idea that may be useful to you.  Thanks for introducing me to the Collatz sequence, it proved interesting.  I modified my Fibonacci workbook to implement the sequence which served to reinforce what I think of as 'the anatomy of a recursive Lambda function.  I have yet to achieve a consistent development and testing strategy though.

I modified the Macro that uploads Lambda formulas from the worksheet to allow the option of cancelling out and so leaving the Lambda definition unaltered (more accurately, to copy the formula before deleting it, so that it can be reinstated if the changes cause the formula to fail.  I have also included a small Lambda function to collect the scalar values returned, last first, from the recursion stack as an array.  

I have yet to decide whether Lambdas are a novelty, (to be brought out to show off or at times of extreme need) or whether they provide the basic building blocks of future Excel solutions.

Viz 

I hadn't realised there was a party going on here!!!

I am turning up late but I hope to be forgiven.

My version is similar but I think there is a difference in that I only accumulate the individual numbers from the sequence after the stack has been fully traversed, allowing the result array to be built after the return from each recursion. 

= LAMBDA(r,n₀,Fᵣ₋₁,Fᵣ₋₂,
  LET(
      Fᵣ, Fᵣ₋₁ + Fᵣ₋₂,
      seq, IF(r<n₀, FIB(r+1,n₀,Fᵣ,Fᵣ₋₁), 0),
      IF(r=SEQUENCE(n₀), Fᵣ, seq) )
  )(2,8,0,1)

To save the user from needing to initialise the recursion, I have used a wrapper function

= FIBONACCI(20)

= LAMBDA(n, FIB(2,n,0,1))(8)

as have others.

SergeiBaklan Good point. I think FIB should probably truncate decimals to integers if entered as parameters to be consistent with other functions. It seems not much change is required to do that because SEQUENCE and INDEX functions already do this (though to be precise one should check values very close to integer as you say.)

=LAMBDA(n,
        IF(n<3,
        SEQUENCE(n,,0),
        LET(b,FIB(n-1),
             IF(SEQUENCE(n)<INT(n),b,INDEX(b,n-1)+INDEX(b,n-2)))
       ))

Viz  I found this pretty challenging and don't find recursion very intuitive either. I first laid out the expected results for all input values from 1 to 10 horizontally referring to prior results using spill operator and then substituted LET to make it more efficient.

Viz  I should have replied here instead of the other post for further discussion.

Have also tweaked recursive formula for the n=1 case.

FIB:
=LAMBDA(n,
       IF(n<=2,
       SEQUENCE(n,,0),
       LET(b,FIB(n-1),
            IF(SEQUENCE(n)<n,b,INDEX(b,n-1)+INDEX(b,n-2))
       )))