尝试使用递归来解决斐波那契 (javascript)

Question

这就是问题:

给定一个正整数 num，return 所有小于或等于 num 的斐波那契奇数之和。

斐波那契数列的前两个数是 1 和 1。数列中每增加一个数都是前两个数的和。斐波那契数列的前六个数字是 1, 1, 2, 3, 5 和 8.

例如，sumFibs(10) 应该 return 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

四件事

(1) 您没有 return 递归调用的结果，因此它永远不会传递给调用者：

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 2

不用数组累加器也能解决；使用 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)])));

Answer 3

延续传球风格

Continuation passing style 有效地为您提供程序化 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

所谓的流很有趣，因为它们可能会产生无限的值，但我们不必一次计算它们。同样，我们可以用简单的术语定义我们的程序，让有用的原语完成所有艰苦的工作 -

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 ]

尝试使用递归来解决斐波那契 (javascript)

Trying to Use Recursion to solve Fibonacci (javascript)

javascript

recursion

fibonacci