斐波那契递归

fuyi501 发布于2019-08-21 17:13 / 3193人阅读

摘要：无路什么数据结构最后都是队栈吗一行写出斐波那契数列改进写法将找到斐波那契数列的第项问题转化为在一个初始项为和的加法序列序列中，每一项都是前两项的和中找到第项的问题。

常规写法

const Fib1 = n => {
  console.log(`Fib1(${n})`)
  if (n === 0) {
    return 0
  } else if (n === 1) {
    return 1
  } else {
    return Fib1(n - 1) + Fib1(n - 2)
  }
}

console.log(Fib1(5))
// 函数调用顺序
// Fib1(5) Fib1(4) Fib1(3) Fib1(2) Fib1(1) Fib1(0) Fib1(1) Fib1(2) Fib1(1) Fib1(0) Fib1(3) Fib1(2) Fib1(1) Fib1(0) Fib1(1)

可以发现整个过程是二叉树先序遍历的过程。此外，整个过程中多次调用了Fib1(3)、Fib1(2)、Fib1(5)，产生大量冗余的调用。无路什么数据结构最后都是队栈吗？

一行写出斐波那契数列

const Fib1 = n => (n <= 1) ? n : (Fib1(n - 1) + Fib1(n - 2))

改进写法1

将找到斐波那契数列的第n项问题转化为在一个初始项为t0和t1的加法序列（序列中，每一项都是前两项的和）中找到第n项的问题。

求以3和7为初始项的第一个序列中的t6(71)可以转化为求以7和10为初始项的第二个序列中的t5(71)

const Fib2 = n => {
  return AdditiveSequence(n, 0, 1)
}

const AdditiveSequence = (n, t0, t1) => {
  console.log(`AdditiveSequence(${n},${t0},${t1})`)
  if (n === 0) {
    return t0
  } else if (n === 1) {
    return t1
  } else {
    return AdditiveSequence(n - 1, t1, t0 + t1)
  }
}

console.log(Fib2(5))
// AdditiveSequence(5,0,1)
// AdditiveSequence(4,1,1)
// AdditiveSequence(3,1,2)
// AdditiveSequence(2,2,3)
// AdditiveSequence(1,3,5)

改进写法2

求以3和7为初始项的第一个序列中的t6(71)可以转化为求以10和17为初始项的第二个序列中的t4(71)

const Fib3 = n => {
  return AdditiveSequence(n, 0, 1)
}

const AdditiveSequence = (n, t0, t1) => {
  console.log(`AdditiveSequence(${n},${t0},${t1})`)
  if (n === 0) {
    return t0
  } else if (n === 1) {
    return t1
  } else {
    return AdditiveSequence(n - 2, t0 + t1, t0 + t1 + t1)
  }
}

console.log(Fib3(5))
// AdditiveSequence(5,0,1)
// AdditiveSequence(3,1,2)
// AdditiveSequence(1,3,5)

海外云主机私有云波那契数列解斐波树形递归递归编程

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/89278.html

js 实现斐波那契数列(数组缓存、动态规划、尾调用优化)

摘要：根据该规则，返回第个斐波那契数。尾递归函数调用自身，称为递归。一个前端眼中的斐波那契数列解斐波那契数列的实用解法调用栈尾递归和手动优化尾调用优化译我从用写斐波那契生成器中学到的令人惊讶的件事斐波那契数列是以下一系列数字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在种子数字 0 和 1 ...

赵连江 2019-08-23 11:38 评论0 收藏0
递归

摘要：递归概念递归是一种针对简单循环难以编程实现的问题，通过函数调用自身，提供优雅解决方案的技术。拥有基础情况或终止条件来停止递归。这个称之为递归调用。为了避免重新创建字符串，使用递归辅助方法来进行改良。递归概念递归是一种针对简单循环难以编程实现的问题，通过函数调用自身，提供优雅解决方案的技术。递归都具有以下三个要点：使用 if-else 或 switch 语句来引导不同的情况。 ...

alphahans 2019-08-20 12:14 评论0 收藏0
使用js实现斐波那契数列

摘要：前言前几天面试被问到了斐波那契数列的实现以及优化的问题，当时现场卡了挺久的，现在进行一下总结使用实现。题目介绍斐波那契数列又被称为黄金分割数列，指的是这样的一个数列，它有如下递推的方法定义是正整数，请使用实现斐波那契函数。前言前几天面试被问到了斐波那契数列的实现以及优化的问题，当时现场卡了挺久的，现在进行一下总结（使用js实现）。题目介绍斐波那契数列又被称为黄金分割数列，指...

alexnevsky 2019-08-26 13:36 评论0 收藏0
云课堂作业---斐波那契数列的引发的思索

摘要：闭包尾递归循环迭代实现使用方式，主要是看实现思想从图中我们可以很明显的看出，使用尾递归计算斐波那契数列性能完胜直接递归和闭包，特别是当数值比较大的时候，尾递归的作用就越明显。前端微专业JavaScript有一道题目是求斐波那契数列的，一开始没想很多，觉得实现功能自己已经很棒棒了（逃）后面有同学讨论直接递归特别耗费时间，开始考虑使用闭包，看我们讨论的不亦乐乎的大佬也发话了，指点我们这两...

UCloud 2019-08-21 17:42 评论0 收藏0
【剑指offer】8.斐波那契数列

摘要：题目题目描述大家都知道斐波那契数列，现在要求输入一个整数，请你输出斐波那契数列的第项从开始，第项为。基本思路这道题在剑指中实际是当作递归的反例来说的。明显也符合斐波那契数列的规律矩形覆盖我们可以用的小矩形横着或者竖着去覆盖更大的矩形。题目题目描述大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。基本思路这道题在剑指offer中...

sf_wangchong 2019-08-23 14:50 评论0 收藏0
【C语言】玩转递归——学好递归，你需要掌握的知识！

摘要：所以，递归在编程中同样是很重要的一个知识点。举个例子用递归实现求第个斐波那契数。总结起来四个字大事化小继续举斐波那契数的例子三递归是怎样运行的我们通过一道题目来讲解。 ...

Donne 2021-09-09 09:33 评论0 收藏0