Even Fibonnacci Numbers

Question

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 4,000,000, find the sum of the even-valued terms.

Solution

This problem is meant to teach the reader how to think of a recursive problem in an iterative fashion. Recursive solutions can be intellectually stimulating and syntactically elegant, but from my experience, a loop is often better suited to the task.

By understanding the base cases and the nature of the Fibonnaci sequence, you can implement this as an array that references earlier values as needed, as opposed to a recursive nightmare. By simply declaring the initial three values, I don’t even have to test for the special cases of the loop, which would have been the base cases of the recursive implementation.

// Returns the sum of all even fibonacci numbers with values <= n
func sumEvenFib(n int) (sum int) {
	sum = 0
	var fibs = []int{1, 1, 2}
	for n := 2; fibs[n] <= limit; fibs = append(fibs, fibs[n-1]+fibs[n-2]) {
		if fibs[n]%2 == 0 {
			sum += fibs[n]
		}
	}
	return sum
}

Note: Tail recursion exists as a method for implementing certain algorithms and is essentially just as efficient as a loop, but I’m leaving it out because a tail-recursive solution involving function closures or global variables would be unnecessarily complicated.

Question#

Solution#

Question

Solution