Project Euler SeriesThis is a second post of ongoing series based on Project Euler.

You can check out the previous post here.

DisclaimerThis 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 ProblemEach 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 😎

## Top comments (0)