LINQ Recipe No. 2-13: How to Generate Fibonacci Numbers Nonrecursively

Contents

1. Introduction
2. Keywords
3. Problem
4. Solution
5. Discussion
5.1 Fibonacci numbers
5.2 Nonrecursive way to compute Fibonacci numbers
6. Practice: Fibonacci Numbers Generation
7. Conclusions
8. Literature & Links

1. Introduction

Functional programming with LINQ is amazing! In this new LINQ recipe we will be to able to compute Fibonacci numbers in a non-recursive fashion. For this, as we will see soon, we just only need to sum up the last previous numbers.

2. Keywords

• Fibonacci
• Functional programming
• Recursivity

3. Problem

Generate Fibonacci numbers using a nonrecursive algorithm.

4. Solution

LINQ allows us to implement an alternative way to compute Fibonacci numbers just using a generator function, and then apply a simple lambda expression over these numbers with the ForEach method from List<T> generic collection.

5. Discussion

5.1 Fibonacci numbers

The Fibonacci serie is sequence of integer positive values. These numbers are defined by the recursive relation ("Fibonacci number", 2016): 

and these are the base cases or seed values: 

For example: 

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

There are a lot of interesting mathematical facts which are based on this recursive relation; for example: 

• Divisibility properties, 
• Fibonacci primes, 
• Periodicity modulo n, 
• Primality testing

But this series is also expressed in nature: the length of the algae string is at each growth stage is equal to Fibonacci numbers.

But...

5.2 Nonrecursive way to compute Fibonacci numbers

With LINQ we can implement this series using a much faster algorithm: we just need to compute the sum of the last two numbers: this can be accomplished just only using a list data structure to recover the last computed two numbers in the series.

6. Practice: Fibonacci Numbers Generation

In the first place, we must remember that recursion implementations are stateless; this means, in other words, that recursive algorithms are forgetful (Mukherjee, 2014). With this in mind, we need to use a data structure to maintain the computed Fibonacci numbers.

Under that requirement, this is the implementation in LINQ: 

LINQ file NonRecursiveFibonacci.linq [Alternative link][Alternative link]: 

In line 2 we declare and create a List with the parametric type ulong. This will serve us as the data structure to store the computed Fibonacci numbers.

Then, the code defined in lines 6-10 performs these operations: 

• Line 6: Creates a range of integer values from 0 to 200.
• Line 7: Converts the range into a List.
• Lines 8-10: This code computes the Fibonacci numbers following these simple rules: 
• If the given number k is less or equal to 1, the number 1 is added to the list.
• On the contrary, if the previous condition is not met, then the sum of last two numbers in the list are computed.

Finally, the first 53 Fibonacci numbers are shown in the output (line 13).

In this video tutorial an explanation is given to this process: 

7. Conclusions

We have explored a new way to generate Fibonacci numbers: this alternative implementation avoids, eventually, an overflow, and takes less time.

LINQ recipe no. 2-14 will teach us how to generate permutations.

8. Literature & Links

Mukherjee, S (2014). Thinking in LINQ Harnessing the Power of Functional Programming in .NET Applications. United States: Apress.
Fibonacci number (2016, July 4). Retrieved from: https://en.wikipedia.org/wiki/Fibonacci_number

V