Trying To Use Recursion To Solve Fibonacci (javascript)

This is the question: Given a positive integer num, return the sum of all odd Fibonacci numbers that are less than or equal to num. The first two numbers in the Fibonacci sequence

Solution 1:

continuation passing style

Continuation passing style effectively gives you programmatic return. Using a CPS function recursively can make program complexity evaporate into thin air -

const identity = x =>
  x

const sumfib = (n = 0, then = identity) =>
  n <= 0
    ? then(0, 1, 1)  // base case
    : sumfib         // inductive: solve smaller subproblem
        ( n - 1
        , (sum, fib, temp) =>
            then(sum + fib, temp, fib + temp)
        )

console.log
  ( sumfib(0) //  0 = 0
  , sumfib(1) //  1 = 0 + 1
  , sumfib(2) //  2 = 0 + 1 + 1
  , sumfib(3) //  4 = 0 + 1 + 1 + 2
  , sumfib(4) //  7 = 0 + 1 + 1 + 2 + 3
  , sumfib(5) // 12 = 0 + 1 + 1 + 2 + 3 + 5
  , sumfib(6) // 20 = 0 + 1 + 1 + 2 + 3 + 5 + 8
  , sumfib(7) // 33 = 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13
  )

---

loop/recur

loop and recur give us the ability to write recursive programs like the one above, but will not encounter a stack overflow error -

const recur = (...values) =>
  ({ recur, values })

const loop = f =>
{ let r = f()
  while (r && r.recur === recur)
    r = f(...r.values)
  return r
}

const sumfib = (n = 0) =>
  loop           // <-- loop with vars
    ( ( m = n
      , sum = 0
      , fib = 1
      , temp = 1
      ) =>
        m <= 0       // <-- exit condition
          ? sum       // <-- base case
          : recur     // <-- recur with updated vars
             ( m - 1
             , sum + fib
             , temp
             , temp + fib
             )
    )

console.log
  ( sumfib(0) //  0 = 0
  , sumfib(1) //  1 = 0 + 1
  , sumfib(2) //  2 = 0 + 1 + 1
  , sumfib(3) //  4 = 0 + 1 + 1 + 2
  , sumfib(4) //  7 = 0 + 1 + 1 + 2 + 3
  , sumfib(5) // 12 = 0 + 1 + 1 + 2 + 3 + 5
  , sumfib(6) // 20 = 0 + 1 + 1 + 2 + 3 + 5 + 8
  , sumfib(7) // 33 = 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13
  )

---

streamz

so-called streams are interesting because they can possibly generate infinite values, but we don't have to compute them all at once. Again we can define our program in simple terms and let useful primitives do all of the hard work -

const fibs =
  stream(0, _ =>
    stream(1, _ =>
      streamAdd(fibs, fibs.next)))

console.log(streamTake(fibs, 10))
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ]

console.log(streamTake(streamSum(fibs), 10))
// [ 0, 1, 2, 4, 7, 12, 20, 33, 54, 88 ]

We just implement stream, streamAdd, streamSum, and streamTake -

const emptyStream =
  Symbol('emptyStream')

const stream = (value, next) =>
  ( { value
    , get next ()
      { delete this.next
        return this.next = next()
      }
    }
  )

const streamAdd = (s1, s2) =>
  s1 === emptyStream || s2 === emptyStream
    ? emptyStream
    : stream
        ( s1.value + s2.value
        , _ => streamAdd(s1.next, s2.next)
        )

const streamSum = (s, sum = 0) =>
  s === emptyStream
    ? emptyStream
    : stream
        ( sum + s.value
        , _ => streamSum(s.next, sum + s.value)
        )

const streamTake = (s = emptyStream, n = 0) =>
  s === emptyStream || n <= 0
    ? []
    : [ s.value, ...streamTake(s.next, n - 1) ]

Expand the snippet below to verify the results in your own browser -

const emptyStream =
  Symbol('emptyStream')

const stream = (value, next) =>
  ( { value
    , get next ()
      { delete this.next
        return this.next = next()
      }
    }
  )
  
const streamAdd = (s1, s2) =>
  s1 === emptyStream || s2 === emptyStream
    ? emptyStream
    : stream
        ( s1.value + s2.value
        , _ => streamAdd(s1.next, s2.next)
        )
   
const streamSum = (s, sum = 0) =>
  s === emptyStream
    ? emptyStream
    : stream
        ( sum + s.value
        , _ => streamSum(s.next, sum + s.value)
        )

const streamTake = (s = emptyStream, n = 0) =>
  s === emptyStream || n <= 0
    ? []
    : [ s.value, ...streamTake(s.next, n - 1) ]

const fibs =
  stream(0, _ =>
    stream(1, _ =>
      streamAdd(fibs, fibs.next)))

console.log(streamTake(fibs, 10))
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ]

console.log(streamTake(streamSum(fibs), 10))
// [ 0, 1, 2, 4, 7, 12, 20, 33, 54, 88 ]

Solution 2:

Four things

(1) You don't return the result of the recursive call, therefore it does never get passed up to the caller:

sumFibs(4, [1, 1]) -> sumFibs(4, [1, 1, 2]) -> sumFibs(4, [1, 1, 2, 3])
                                            <- [1, 1, 2, 3]
//                                           v the return you do
//                 v the return you need too

(2) In the recursive call, the order of arguments is wrong.

(3) I guess instead of taking the arrays length minus 1, you want to access the property at that position in the total array.

(4) Why do you actually n as an argument? As it is only depending on total, it could also just be a variable:

function sumFibs(num,  total = [1, 1]) {
  const n = total[total.length - 1] + total[total.length - 2];
  if(n > num){
    return total;
  }

  total.push(n);

  return sumFibs(num, total);
}

console.log(sumFibs(19));

Solution 3:

This can be solved without an array accumulator; use n as a counter and curr and prev vars to store the data necessary to compute the Fibonacci series. Whenever we have an odd curr, add it to the running total and pass it up the call stack.

const sumOddFibs = (n, curr=1, prev=0) => {
  if (curr < n) {    
    return sumOddFibs(n, curr + prev, curr) + (curr % 2 ? curr : 0);
  }
  
  return 0;
};

console.log(sumOddFibs(10));

As an aside, recursion is a pretty poor tool for just about anything that involves a sequential 0..n counter. Iteration makes more sense: less overhead, easier to understand and no risk of blowing the call stack. I'd also separate computation of the Fibonacci series (which is a good use case for a generator) from filtering oddness and summing so that each step is independent and can be reused:

const sum = arr => arr.reduce((a, e) => a + e);
const odds = arr => arr.filter(e => e % 2);

function *fibsBelow(n) {
  for (let prev = 0, curr = 1; curr < n;) {
    yield curr;
    const tmp = curr;
    curr += prev;
    prev = tmp;
  }
}

console.log(sum(odds([...fibsBelow(10)])));