Project Euler 2 - Fibonacci sequence

I lately spend a lot of time at Project Euler programming challenges. I have following problem which I should solve:


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.

I wrote Java code and I submitted it.

Implementation

First, I wrote helper method fibonacci(int n) which calculates a n-th word of fibonacci sequence and returns it. In main method I created a list of numbers and a n variable, that would be incremented in a loop. In the loop I was looking for all numbers that are even-valued that are added to the list. Next, I created result variable and I sum all numbers in the list and then, finally I printed it out to console.

Main.java:

package pl.hubot.projecteuler.problem2;

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List numbers = new ArrayList<>();
        int n = 0;
        while (fibonacci(n) < 4_000_000) {
            if (fibonacci(n) % 2 == 0) numbers.add(fibonacci(n));
            n++;
        }
        int result = 0;
        for (Integer number : numbers) {
            result += number;
        }
        System.out.print(result);
    }

    private static int fibonacci(int n) {
        if (n == 0) return 0;
        else if (n == 1) return 1;
        else return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

The recursive definition of Fibonacci is an elegant one, but in practice it's something you would never want to use. Let's say you want to get fibonacci(5). How often does fibonacci get called?

fibonacci(5)
 =    fibonacci(4) + fibonacci(3)
 =   (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
 =   ((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0)))
   + ((fibonacci(1) + fibonacci(0)) + fibonacci(1))
 =   (((fibonacci(1) + fibonacci(0)) + fibonacci(1)) 
        + (fibonacci(1) + fibonacci(0))
     )
   + ((fibonacci(1) + fibonacci(0)) + fibonacci(1))

That seems a lot for 0 + 1 + 1 + 2 + 3 + 5. Indeed, the recursive variant without memoization has exponential runtime. You have several options to reduce the time:

• use an iterative variant (which leads to \$ \mathcal O(n)\$ instead of \$ \mathcal O(2^n)\$ per call of fibonacci),

• use memoization (which, if done correctly, leads to \$ \mathcal O(n)\$ in worst case and \$ \mathcal O(1)\$ if the number was already calculated).

But that begs the question: do we actually need fibonacci? For a programming challenge, it's enough to calculate the sum in main, while you're calculating the numbers iteratively. If you're looking for performance, that would be the fastest variant (that doesn't use the closed form).

StackExchange Code Review Q#162316, answer score: 6