Пытаясь использовать рекурсию для решения Фибоначчи (javascript)

Question

Это вопрос :

Если задано положительное целое число num, вернуть сумму всех нечетных чисел Фибоначчи, которые меньше или равны num.

первые два числа в последовательности Фибоначчи - 1 и 1. Каждое дополнительное число в последовательности является суммой двух предыдущих чисел. Первые шесть чисел последовательности Фибоначчи - 1, 1, 2, 3, 5 и 8.

Например, sumFibs (10) должно возвращать 10, потому что все нечетные числа Фибоначчи, меньшие или равные 10, равны 1 , 1, 3 и 5.

Это то, что я пытался

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);

};

Вопрос

Возможно ли это использовать мой метод, чтобы сделать эту работу, если так, как я могу исправить синтаксис? Если нет, то как бы вы решили проблему.

Большое спасибо!

Answer 1

стиль передачи продолжения

Стиль передачи продолжения эффективно обеспечивает программирование c return. Использование рекурсивной функции CPS может привести к тому, что сложность программы превратится в воздух -

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 и recur дают нам возможность писать рекурсивные программы, такие как один выше, но не встретит ошибку переполнения стека -

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

так называемые streams интересны тем, что могут генерировать бесконечные значения , но нам не нужно вычислять их все сразу. Опять же, мы можем определить нашу программу в простых терминах и позволить полезным примитивам выполнить всю тяжелую работу -

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 ]

Мы просто реализуем stream, streamAdd, streamSum и 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) ]

Разверните фрагмент ниже, чтобы проверить результаты в своем собственном браузере -

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 ]

Answer 2

Четыре вещи

(1) Вы не возвращаете результат рекурсивного вызова, поэтому он никогда не передается вызывающей стороне:

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) В рекурсивный вызов, порядок аргументов неправильный.

(3) Я полагаю, вместо длины массива минус 1, вы хотите получить доступ к свойству в этой позиции в массиве total.

(4) Почему вы на самом деле n в качестве аргумента? Поскольку он зависит только от total, он также может быть просто переменной:

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));

Answer 3

Это можно решить без накопителя массива; используйте n в качестве счетчика и curr и prev переменные для хранения данных, необходимых для вычисления ряда Фибоначчи. Всякий раз, когда у нас есть нечетное curr, добавьте его к промежуточному итогу и передайте его в стек вызовов.

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));

Кроме того, рекурсия - довольно плохой инструмент для всего, что связано с последовательным счетчиком 0..n. Итерация имеет больше смысла: меньше накладных расходов, легче понять и нет риска перебросить стек вызовов. Я бы также отделил вычисление ряда Фибоначчи (который является хорошим вариантом использования для генератора) от фильтрации нечетности и суммирования, чтобы каждый шаг был независимым и мог использоваться повторно:

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)])));