2

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 are 1 and 1. Every additional number in the sequence is the sum of the two previous numbers. The first six numbers of the Fibonacci sequence are 1, 1, 2, 3, 5 and 8.

For example, sumFibs(10) should return 10 because all odd Fibonacci numbers less than or equal to 10 are 1, 1, 3, and 5.

This is what I tried

function sumFibs(num,  total = [1, 1], n = (total.length - 1 + total.length - 2)) {

if(n == num){
return total;
}

total.push(n);

sumFibs(num, n = (total.length - 1 + total.length - 2), total);

};

Question

Is it possible to use my method to make this work, if so how do I fix the syntax? If not, how would you solve the problem.

Many thanks!

Aplet123
  • 33,825
  • 1
  • 29
  • 55
AndrewNeedsHelp
  • 385
  • 4
  • 15

3 Answers3

2

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 ]
Mulan
  • 129,518
  • 31
  • 228
  • 259
  • 2
    Fascinating! I haven't seen streams done like that before. I can't yet grok the advantages/disadvantages compared to generator functions, but I really love seeing this alternative. – Scott Sauyet Apr 22 '20 at 21:45
  • It is also clear how to write `streamLimit` and `streamFilter` so that the problem as posed can be solved with `const sumFibs = (limit) => sum (streamLimit (streamFilter (fibs, isOdd), limit))` (given obvious `isOdd` and `sum` functions.) This is nice stuff! – Scott Sauyet Apr 22 '20 at 22:04
  • One notable advantage is these streams are functional (persistent, immutable) and memoised. `streamTake(s, 10)`, will compute the first 10 elements, but a subsequent `streamTake(s, 13)` will only compute another 3 elements. The big difference is `streamTake(s, 13)` can still access the first 10 elements, whereas JavaScript generators can never rewind after `.next`-ing. – Mulan Apr 23 '20 at 06:23
  • 1
    ... with the obvious disadvantage of consuming memory for memoization. Whatever, (another) really cool answer of you, naomik :) – Jonas Wilms Apr 24 '20 at 09:08
  • Scott, I also wanted to share [this stream implementation](https://stackoverflow.com/a/57813405/633183) with you. I couldn't find it when I was looking for it last week, but another question from today helped me unbury it :D – Mulan Apr 27 '20 at 17:50
  • 1
    @JonasWilms thanks. I wouldn't really consider the memoization a _cost_ in this situation. If the persistent iterator is to "hold" the data for repeated consumption, it must be stored somewhere. The memory is released as soon as the stream is released. If a stream is only going to be consumed once, then yes, caching the computed stream tails is a waste. Thanks for the comment. It was nice to hear from you and I hope you are doing well ^^ – Mulan Apr 27 '20 at 17:52
1

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));
Jonas Wilms
  • 132,000
  • 20
  • 149
  • 151
  • To add another layer of complexity to this, we need to only apply this to odd numbers, I tried: function sumFibs(num, total = [1, 1]) { const n = total[total.length - 1] + total[total.length - 2]; if(n > num){ return total; } if(n%2 == 0) { total.push(n); } return sumFibs(num, total); } sumFibs(4); But it leads to a maximum call stack size exceeded – AndrewNeedsHelp May 16 '20 at 12:49
0

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)])));
ggorlen
  • 44,755
  • 7
  • 76
  • 106
  • It might read better to replace the last three lines of the loop with `[prev, curr] = [curr, prev + curr] ` – Scott Sauyet Apr 22 '20 at 17:36
  • It depends. If the code is running without compilation, then it's a question of whether you are willing to take the performance hit of two object allocations and garbage collections. If you can transpile it out, then the readability is definitely better and there's no performance hit. – ggorlen Apr 22 '20 at 17:43