Photo by As an employee of JetBrains, I get to see and interact with many languages and technology stacks; frankly, it’s pretty rewarding. While I would still say my expertise is C#, these experiences inform my thoughts on C# and .NET in general: What’s good? What could be better? These questions help me gain new perspectives I otherwise wouldn’t have if I had stayed inside my ecosystem bubble.
As a recent exercise, I thought I’d implement the Fibonacci sequence in both Kotlin and C# and I decided to share it on Twitter. The responses from the community have been surprising and educational. So I thought I would take the best solutions and share them here in this post.
What is the Fibonacci sequence?
The Fibonacci sequence is a pattern commonly found in nature and has been described as early as 200 BC in Indian Mathematics. The sequence was introduced to Western European mathematics by Leonardo of Pisa, later known as Fibonacci.
The sequence works by starting with the values of 0 and 1, then proceeding to derive the next value by calculating the sum of the two previous values. Here are the first 13 digits of the sequence.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
As you can see, the numbers quickly snowball in magnitude. Therefore, the mathematical formula for the sequence is as follows.
F0 = 0, F1 = 1
and then
Fn = Fn-1 + Fn-2
Read more about it on Wikipedia; it is a fascinating topic.
It’s simple enough to program using a language, but you can tackle this simple equation in many ways as a programmer. So let’s first look at my solutions in both Kotlin and C#.
My Fibonacci Sequence Solutions
Kotlin is a language developed by JetBrains and has functional and object-oriented concepts. It is a JVM-based language focusing on interop between itself and Java. If you’re familiar with C#, you’ll likely find it pleasant to read and write Kotlin. So let’s take a look at the solution written with the use of Kotlin.
The first implementation is a declarative style, similar to what you’d see with LINQ in C#.
fun fibonacci(num: Int): List<Int> {
val series = mutableListOf(0, 1)
(2..num)
.asSequence()
.map { series[it -1] + series[it -2] }
.forEach { series.add(it) }
return series
}
I also wrote an imperative style, using a for loop.
fun fibonacciLoop(num: Int) : List<Int> {
val series = mutableListOf(0, 1)
for(i in 2..num) {
series.add(series[i - 1] + series[i - 2])
}
return series
}
Finally, let’s look at the C# solution. Note I had to write a few extension methods to get a similar syntax to the Kotlin solution. I did so because I started this experiment trying to get two similar answers across technology stacks.
var series = Fibonacci(10);
Console.WriteLine(string.Join(",", series));
IReadOnlyList<int> Fibonacci(int num)
{
var series = new List<int> { 0, 1 };
(2..num)
.AsSequence()
.Select(it => series[it - 1] + series[it - 2])
.ForEach(it => series.Add(it));
return series.AsReadOnly();
}
public static class KotlinExtensions
{
public static IEnumerable<int> AsSequence(this Range range) {
for (var i = range.Start.Value; i <= range.End.Value; i++)
yield return i;
}
public static void ForEach<T>(this IEnumerable<T> seq, Action<T> action)
{
foreach (var item in seq) action(item);
}
}
As you can see, I’ve written two extension methods of AsSequence and ForEach. You may say, “But Khalid, List has a ForEach method!” I would have to iterate the original collection, breaking the enumeration necessary to solve the solution.
Those are my solutions, but I quickly found out there are more C# solutions. Let’s look at some of them that veer away from the Kotlin-looking implementation and rely more on C# and .NET features.
Community Solutions
I want to thank the following community members that shared these solutions: Jeremy Sinclair, Ian Russell, Ian Griffiths, and Krimog. Let’s take a look at a few. Some focused on elegance, while others concentrated on allocations and performance. Try them out to see which ones suit your needs.
The first is an implementation that stores the values in a collection and finds the values using a for loop. Simple and understandable.
IReadOnlyList<int> Fibonacci(int num)
{
var series = new List<int> { 0, 1 };
for (var i = 2; i <= num; i++)
{
series.Add(series[i - 1] + series[i - 2]);
}
return series.AsReadOnly();
}
The following solution from Ian Griffiths uses the yield operator and can go “forever”. It is up to the caller to determine if they need to store the values or just throw them away as they iterate. It also uses a neat deconstruction technique to swap values as the loop continues.
using System.Numerics;
var series = FibonacciEndless().Take(10);
Console.WriteLine(string.Join(",", series));
IEnumerable<BigInteger> FibonacciEndless()
{
BigInteger i = 0, n = 1;
while (true)
{
yield return i;
(i, n) = (n, i + n);
}
}
A modified solution from Jeremy Sinclair uses the Aggregate construct to build a collection.
var series = Fibonacci(10);
Console.WriteLine(string.Join(",", series));
IReadOnlyList<int> Fibonacci(int num)
{
return Enumerable
.Range(2, num - 1)
.Aggregate(new List<int> { 0, 1 }, (it, next) =>
it.Append(it[next - 1] + it[next - 2]).ToList()
).AsReadOnly();
}
The following solution is from Krimog, which uses the yield operator again with the technique of streaming values as you iterate. This is likely the most memory efficient approach.
var series = Fibonacci().Take(10);
Console.WriteLine(string.Join(",", series));
IEnumerable<int> Fibonacci()
{
yield return 0;
yield return 1;
var current = (n0: 0, n1: 1);
while (true)
{
current = (current.n1, current.n0 + current.n1);
yield return current.n1;
}
}
Finally, we have a solution written in F# by Ian Russell. The answer is neat as it uses the unfold function and is unique to F#.
let fib n =
Seq.unfold
(fun (n0, n1) ->
Some(n0, (n1, n0 + n1)))
(0I, 1I)
|> Seq.take n
let run = fib 11 |> Seq.toList |> printf "%A"
That’s pretty cool!
Conclusion
I started this exercise to learn more about Kotlin, and sharing my work with the community yielded more solutions that helped me understand .NET better and solve the Fibonacci sequence with C# and F#. If you have other approaches you’d like to share, please follow me on Twitter @buhakmeh and tweet me directly. As always, thank you for reading.
