Project Euler question 2 in CoffeeScript

Question

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

fib = (x) ->
  return 0 if x == 0
  return 1 if x == 1
  return fib(x-1) + fib(x-2)

i = 2
fib_sum = 0

while (fib i) < 4000000
  n = fib i 
  if n % 2 is 0 then fib_sum += fib i
  i++

alert fib_sum

I am looking for a more "functional" solution but I am stuck.

Edit

Optimized the solution:

limit = 4000000

sum = 0
a = 1
b = 1

while b < limit
  if b % 2 is 0 then sum += b
  h = a + b
  a = b
  b = h

alert sum #4613732

Answer 1

Better CoffeeScript

First of all, if you're going to use CoffeeScript, then use its full potential and do away with h:

limit = 4000000
sum = 0 

[a, b] = [1, 1]

while b < limit
  sum += b if b % 2 is 0
  [a, b] = [b, a + b]

console.log sum

It's nice and easy to read, and I'd use this implementation instead of a recursive one in "real code", but it's still instructive to think about a functional equivalent.

Memoization

What you're looking for is named memoization. The trick is that you should store the values of fib(n) in an array. This allows you to lookup in the array for most cases instead of computing the value again. You'll be able to use fib() in a natural but optimized way.

memo = [1, 1]

fib = (x) ->
    if typeof memo[x]  != 'number'
        memo[x] = fib(x - 1) + fib(x - 2)

    return memo[x]

Now we have a function that compute memo[x] if needed, and returns it for every call. This means that the first call to fib(3) is going to compute it using memo[2] and memo[1], but all subsequent calls are going to be "free".

I can now use this implementation to compute the sum over even values:

fib_sum = (i) ->
    // Initialize i to 0 for the first call
    if i is undefined then i = 0

    return 0 if fib(i) > limit

    if fib(i) % 2 == 0
        return fib_sum(i + 1) + fib(i)
    else 
        return fib_sum(i + 1)

You can use a tail-recursive function if you want but this won't help since you're probably going to overflow before doing a stack overflow.

Purely functional from the outside

Now the implementation seems functional but there's still this "memo" array that we would like to hide. Well, closures are the perfect way to achieve this. This is called the "pattern module" in JavaScript. Here's the full code:

fibonacci = (() ->
    'use strict'

    memo = [1, 1]
    limit = 4000000

    fib = (x) ->
        if typeof memo[x]  != 'number'
            memo[x] = fib(x - 1) + fib(x - 2)

        return memo[x]

    even_sum = (i) ->
        if i is undefined then i = 0

        return 0 if fib(i) > limit

        if fib(i) % 2 == 0
            return even_sum(i + 1) + fib(i)
        else 
            return even_sum(i + 1)

    return {nth: fib, even_sum: even_sum}
)()

console.log fibonacci.even_sum(); # 4613732

There's no way to know that out fibonacci module uses an array internally, but it's still used and allows for very fast code. Benchmarking show that it's as fast as the iterative version, and takes about 0.02s on my machine.

Automatic memoization?

It turns out that JavaScript: The Good Parts mentions that you can have automatic memoization and uses fibonacci as an example. It can be interesting to try to apply this to our fib_sum, but I'll leave it as an exercise. :)