Project Euler Series

This is a second post of ongoing series based on Project Euler.
You can check out the previous post here.

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 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!

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:

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

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:

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
and on this blog.

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 😎