Lambda Example: Generate Fibonacci series

Brass Contributor

In this post, I would like to explain how I have used Lambda to create a function to generate a Fibonacci series array.

 

This example can also be used to understand how to create an array where the value of an element in the array depends on previous elements in the same array.

 

Generating Fibonacci as a dynamic array by @VizGenerating Fibonacci as a dynamic array by @Viz

 

This function has been created using three function in two layers. The inner layer functions include the following:

InFib: This function generates the Nth Fibonacci number

InFibSer: This function generates the entire Fibonacci series up to the Nth number

 

The two functions mentioned above require arguments that are complicated and less intuitive. Therefore, we use an outer layer function (FibSeries) that generates the necessary argument and calls the two functions to generate the series.

 

=InFIB

'This function returns nth Fibonacci using tail recursion
'It takes three arguments n, a=0 , b=1 as argument and returns the nth Fibonacci value

 

 

=LAMBDA(n,a,b,IF(n=1,a,IF(n=2,b,Infib(n-1,b,a+b))))
/* The value for the arguments a and b should be passed as 0 and 1, respectively. */

 

 

 

Example:

=InFIB(10,0,1) would generate 34 as the value

 

Our objective, here, is not to obtain a single value but to generate an entire array. However, here is where we have a challenge: While it is easier to manipulate an existing array, it is far more to difficult to create a new array (other than sequence array) or extend an existing array.

 

Therefore, in order to create a Fibonacci series, we are going to pass a dummy array of n values. This array will have 0 as the first element and 1 as the value for all the other elements.

 

The following image portrays the recursive addition process that converts that the initial array into a Fibonacci series.

 

Fibonacci algo illustration.png

 

The following code does carries out the process recursively till the maximum value of the array equals the nth Fibonacci value.

 

=INFIBSER

'This inner function takes three arguments and returns a Fibonacci series
'The three arguments are nth Fibonacci value, the initial array and a sequence array (sequential numbers from 1 to n)
'Note, the sequence array can instead be generated inside the function but it may inefficient

 

 

=Lambda(NthFib, Initval, Sqn,
	Let(
	    Maxval,Max(Initval),
	    If(Maxval = NthFib,
		Initval,
		Let(
		    NewVal,If(Maxval=1,Initval+1*(Sqn>=4),
		              Let(
			          StPos,Match(Maxval,Initval,0)+1,
			          adval,Large(unique(Initval),2),
			          Initval+adval*(Sqn>=StPos)
		                  )
			     ),
		    InFibser(NthFib,NewVal,Sqn)
		)
	)
)
 )

 

 

 

In the first iteration, the above function adds one to all the values from the fourth position onwards. For the subsequent iterations it adds the second largest unique value to all values that all 2 places after the position of such second largest value. The above function uses the match function to identify the position pointer.

 

Although the above function can generate the Fibonacci series, as mentioned earlier, it requires arguments that are less intuitive and which requires some set up.

 

Therefore, here we have an outer layer function that requires only one argument, n. It creates the necessary argument to be passed to the inner layer function and calls them.

 

=FIBSERIES

'This outermost function generates an initial array, a sequence array, and nth fibonnaci value
'It then calls the inner functions with these parameters 

 

 

 

=Lambda(n,
	Let(
		Sqn,sequence(n),
		initval,sign(Sqn-1),
		Nthfib,Infib(n,0,1),
		InFibser(Nthfib, Initval, Sqn)
	)
 )

 

 

 

This final function can be used by the user to generate the Fibonacci series by merely passing the number of values required as argument.

 

Hope you found this useful. I would love to know if you think there is a way to improve the algorithm, here. I am especially looking for suggestions that could replace the match / xmatch in the InFibSer function to get the position pointer. Since the positions move sequentially, I believe a mathematical solution may exist.

 

Thank you

82 Replies

@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))
       )))

 

@lori_m 

If add error handling as

=LAMBDA(n,
       IF(n<>INT(n),"use integer as argument",
       IF(n<=2,
       SEQUENCE(n,,0),
       LET(b,FIB(n-1),
            IF(SEQUENCE(n)<n,b,INDEX(b,n-1)+INDEX(b,n-2))
       ))))

it returns errors message as expected for FIB(10.1), but the spill as

image.png

for FIB(10+1e-14). Correction could be

=LAMBDA(n,
   IF(n<>INT(n),"use integer as argument",
      LET(m, INT(n),
         IF(m<=2,
         SEQUENCE(m,,0),
         LET(b,FIB(m-1),
         IF(SEQUENCE(m)<m,b,INDEX(b,m-1)+INDEX(b,m-2))
   )))))

@lori_m 

 

Wow! your solution is super elegant!

 

I was initially trying something closer to your first solution but I could not crack the logic to extend the size of array. And the algorithm I used to extend the array made the function very slow.

 

I am still getting my head around your function to understand how the array is getting extended. But thank you very much for sharing these solutions. It was very useful.

@Sergei Baklan 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.

@lori_m 

In case of FIB() - yes, maybe, but the question is more general. How to find the compromise with error handling within lambdas which definitely could reduce the performance. Keep #VALUE! and #N/A as in native functions or add error handling and when. Decision is on case by case basis, I don't see common rule.

Another side effect is rounding which could give an error only on some inner iteration if use recursion, probably it will be bit hard to debug in some cases.

@Sergei Baklan @lori_m 

 

There may be a better solution but one approach I can think about handling error would be to have Lambda in two layers.

 

I am just putting the pseudo code here,

 

MAIN

=Lambda(n, IF(n<>int(n),"Enter integer",FIB(n)))

 

FIB

=Lambda(n, ..................)

 

I am new to recursive programming. So, I am not sure if this is the only solution. Perhaps better option exists.

@Viz 

The problem is that =n=INT(n) could return TRUE for the first iteration and FALSE on next ones if the difference is around 14th digit.

@Sergei Baklan 

In this case error handling could be carried out by wrapping in another function as suggested by @Viz , the n = INT(n) condition is not iterated then. In general there will be the performance/error propagation considerations you mention so better to avoid adding extra conditions inside recursive functions if possible.

@lori_m 

That's the question better to avoid or better not to avoid. I guess LAMBDA(), as well as simple LET(), don't improve the performance themselves compare to set of formulas and named cells/ranges, suspect they decrease it. What they improve that's flexibility and maintainability. From this point of view perhaps better not to avoid if only performance not becomes a critical issue for the concrete project. Again, I don't care about Fibonacci case, that's only an example.

@Sergei Baklan 

I suspect you are right that while LAMBDA / LET solutions may add flexibility and maintainability they may often be a little less efficient than more traditional solutions involving helper ranges.

 

For discussion it's helpful to have some concrete examples in mind. Many common problem scenarios involving manipulating data tables in various ways could be implemented using DA methods without the need for recursion in which case inserting extra conditions is not much of an issue particularly if these conditions can be hidden from view inside LAMBDA so as not to be a source of distraction.

 

One broad class of problem where recursion would generally be required are formula solvers. For financial models obvious examples include yield-to-maturity, implied volatility and bootstrapping (curve fitting) calculations. Here the objective is to find a solution to a model which is satisfied within a given bound. IMHO an idealistic approach for these type of cases would keep the recursive code compact so it can be easily translated into business logic and use wrapper functions for implementing any additional conditions as suggested above.

@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.

image.png

@lori_mWas struggling to figure out how to extend an array as well, thanks for this example. Using your FIB array extension as a hint I've got a generic iterator layout after struggling with the formula a bit. Formula was returning a #NUM error, and figured out that TYPE(INDEX(Seed,ROWS(Seed)))=64 (array) rather than 1 for number. Any ideas on better way to do this? Decided to work through Project Euler problems to wrap my head around LAMBDA usage and this is part of my solution to question on Collatz sequence.

 

=LET(n,<cell_ref or hardcode number>,
         LET(Next,LAMBDA(Prior,IF(ISEVEN(Prior),Prior/2,Prior*3+1)),
                Seed,SEQUENCE(1,1,n,0),
                Iterate,LAMBDA(ME,Seed,
                           LET(PriorVal,NUMBERVALUE(ARRAYTOTEXT(INDEX(Seed,ROWS(Seed)))),
                                 CurrVal,Next(PriorVal),
                                 CurrResult,IF(SEQUENCE(ROWS(Seed)+1)<(ROWS(Seed)+1),Seed,CurrVal),
                                 IF(PriorVal=1,Seed,IF(CurrVal=1,CurrResult,ME(ME,CurrResult)))
                           )
                 ),
                Iterate(Iterate,Seed)
         )
)

@tboulden 

I have still to get to grips with your formula; I find recursive formulae especially opaque!

One observation, though.  It is possible to conduct the recursion, and maintain a counter that could be used as a backup termination criterion, without building the array as you go.

When the end point is reached, all the values obtained along the way are still present within the memory stack and are accessible one at a time following return from the previous level.  In the Fibonacci example I used this to combine the current value and the return array to build the complete series as an array of known length.

@Peter Bartholomew 

It's known that recursive lambda allows quite limited number of iteration. I tried to play with different variants of FIB() presented to find max allowed parameter for each. Actually that's about number of iteration, we are within max returned number limit.

image.png

In last case I just added text constant within LET().

That's not an analysis, just stats. 

Thanks Peter, I reviewed your version, and translated it for my case; I'll have to experiment with it some, but for this particular problem, I run up against the stack depth (about 170ish recursions deep with the parameter count/setup I'm using). I'm pleased that with your version, I avoid the NUMBERVALUE(ARRAYTOTEXT(INDEX(...))) usage, though I imagine there is probably a better way to handle that as well. Thanks again!

PS: Part of wrapping my head around this is has been this useful post: https://www.sumproduct.com/news/article/lambda-formulaic-recursion-its-all-about-me

@tboulden 

Your Collatz example looks intriguing I will try and make time to look. And thanks for that useful link; it is stated near the end that: 

 

"do note that the current operand stack limit in Excel is 1,024.  This should be borne in mind together with calculation times, as the current recursion limit is set as 1,024 divided by (number of lambda parameters + 1)."

 

The 1024 stack limit does seem to tally with Sergei's results further up. It appears that the figures all roughly divide 1024 (within a few units of rounding):

341 ~ 3 stack operands per call

256 ~ 4 stack operands per call

146 ~ 7 stack operands per call

This also suggests other parameters may need to be taken into account in addition to lambda parameters.

@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.

 

image.png

Peter, you surely know how to make a nice presentation! Will take some time and review what you've set up here. Thanks very much!

@Peter Bartholomew I don't know where to begin writing this reply but thank you for providing that mighty Lambda of yours for the Fibonacci Sequence.  :backhand_index_pointing_right:🤯:backhand_index_pointing_left: Below is the result of visualizing that function combined with the works of Tim Wolverson on plotting this beautiful sequence of numbers in Excel. If interested in Tim's work go here :backhand_index_pointing_right: https://lnkd.in/dtYKEj34  

For anyone interested in the workbook of the image below go here :backhand_index_pointing_right:
 https://lnkd.in/dVDJCafX

 1.png

To all of you in this discussion, thank you! :folded_hands: