Project Euler #2 - does Fibonacci have a tail?
Tags: kotlin, projecteuler, programming, beginners
Published: 2022-12-29 11:12:47

> **Project Euler Series**
>
> This is a second post of ongoing series based on [Project Euler](https://projecteuler.net/).
> You can check out the previous post [here](https://dev.to/fangcode/project-euler-1-are-we-fizz-buzzing-4k85).

> **Disclaimer**
>
> This blogpost provides solution to the 2nd problem from Project Euler. If
> you want to figure out a solution yourself, go to the
> [Problem 2's page](https://projecteuler.net/problem=2) and come back later :)

The 2nd task is a bit more complex than the previous one, especially for a 
person who hasn't dealt with typical algorithmic problems. This one touches 
[Fibonacci sequence](https://en.wikipedia.org/wiki/Fibonacci_number)! 

> **The Problem**
>
> Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
> 
> 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
>
> By considering the terms in the Fibonacci sequence whose values do not 
> exceed four million, find the sum of the even-valued terms.

The Fibonacci Sequence is a common example for recursive algorithm's 
implementation. If you want to get an `n` value from the sequence your 
implementation may look something like this:

```kotlin
private fun fib(n: Int): Int =
    if (n <= 1) {
        n
    } else {
        fib(n - 1) + fib(n - 2)
    }
```

However, in our problem, we need to get every value from the sequence until 
`4_000_000`, in order to check if it is even and sum them. So, we 
definitely need some accumulator.

## The Solution

```kotlin
private tailrec fun sumOfEvenFibonacciNumbers(
    evenAcc: Int,
    prev: Int,
    current: Int,
    top: Int
): Int {
    val next = prev + current
    return if (next >= top) {
        evenAcc
    } else {
        val newAcc = if (next.isEven()) {
            evenAcc + next
        } else {
            evenAcc
        }
        sumOfEvenFibonacciNumbers(
            evenAcc = newAcc,
            prev = current,
            current = next,
            top = top,
        )
    }
}

private fun Int.isEven() = mod(2) == 0
```

In order to get the solution I call it like this:

```kotlin
println(
    sumOfEvenFibonacciNumbers(
        evenAcc = 0,
        prev = 1,
        current = 1,
        top = 4_000_000,
    )
)
```

## tailrec
Maybe, you noticed I used `tailrec`. In that case, it's not really 
needed, but I added it as a fun fact 🥸 `tailrec` is an information to the 
kotlin's compiler that our function is a tail-recursive function. This means,
we can implement our algorithm using recursion without being scared about 
the `StackOverflowException` and the compiler will rewrite it into 
imperative manner.

This sounds great, however a function must be written in a 
certain way. The recursive call must happen at the end of the function. In 
other words, the recursive call must be the last thing a function does. You 
can read more about it in the [Kotlin's docs](https://kotlinlang.org/docs/functions.html#tail-recursive-functions)
and [on this blog](https://www.baeldung.com/kotlin/tail-recursion).

## Conclusion
Different approach to dealing with the Fibonacci sequence was fun and 
allowed to explore recursion again which I haven't used for some 
time.

I invite you to continue this little journey with Project Euler to not only 
figure out next problems but to have fun with some concepts and sometimes 
dig deeper.

Cheers 😎