cnu摄影网站,wordpress主页显示全文,网站关于页面,app开发设计方案怎么写递归 1.递归应该一种比较常见的实现一些特殊代码逻辑时需要做的#xff0c;但常常也是最绕的一种方式#xff0c;在解释递归 之前#xff0c;我们用循环和递归来做个比较1.1.如果你打开一扇门后#xff0c;同样发现前方也有一扇们#xff0c;紧接着你又打开下一扇门...直… 递归 1.递归应该一种比较常见的实现一些特殊代码逻辑时需要做的但常常也是最绕的一种方式在解释递归 之前我们用循环和递归来做个比较1.1.如果你打开一扇门后同样发现前方也有一扇们紧接着你又打开下一扇门...直到打开最后一扇门出去 或者一直没有碰到尽头 死循环——这就是循环1.2.如果你打开一扇门紧接着你又用钥匙打开了这扇门然后你又看到一扇们...但是当你开到某扇门时 发现前方是一堵墙无路可走了你选择原路返回——这就是递归2.通过上面的故事可以发现递归其实是两个过程2.1.递问题分解去的过程叫递 -- 就像故事打开的门2.2.归遇到终止递的条件叫归 -- 就像故事里的墙 满足递归的条件
1.递归是一种解决问题的方法它从解决问题的各个小部分开始直到解决最初的大问题。递
归通常涉及函数调用自身
2.还是上面开门的故事你想知道你开启的第一个门实际是距离墙的第几扇门这个问题想要解决
根据第一条的概念进行拆分2.1.分解成各个小部分也就是我要知道我下一扇门距离墙是第几扇门2.2.这个问题与分解之后的子问题除了数据规模不同求解思路完全一样,我想知道开启第一扇门距离墙是第几扇门和我想知道下一扇门距离墙的位置是第几扇门是一样的2.3.存在递归终止条件,也就这些问题一层一层解析后直到我知道扇的位置后终止在一个个回来数
如何编写递归
1.写出递推公式找到终止条件
2.写递归代码的关键就是找到如何将大问题分解为小问题的规律并且基于此写出递推公式然后再推敲终止条件
最后将递推公式和终止条件翻译成代码
3.编写递归代码的关键是只要遇到递归我们就把它抽象成一个递推公式不用想一层层的调用关系不要试图用人
脑去分解递归的每个步骤
递归到底是个什么
1.递归就是栈一种应用场景也遵循着先进后出的原则后进先出 递归阶乘
1.求5*4*3*2*1 的问题用递归来解决三步走1.1.分解成各个小部分5 * fn(4) 参数n 5-15 * (4*fn(3)) 参数n 4-15 * 4 * (3*fn(2)) 参数n 3-15 * 4 * 3 * (2*fn(1)) 参数n 2-11.2.推到成递归公式 fn(n) n*fn(n-1) ,且fn(1) 11.3.终止条件 fn(1) 1// 代码
1.递归是栈的结构表现所以它递的过程是在做压栈归的过程在做出栈其实本质先算的是
终止条件然后在依次向上传递
2.如图一通过浏览器的控制台可以更形象的看出这个过程function factorial(n){console.trace()if(n 1 || n 0){return 1}console.log(n)return n * factorial(n-1)
}
factorial(5) 斐波那契数列
01123581321
// 斐波那契数列
function fibonacciIterative(n){if(n 1) return 0 // 结束条件if(n 2) return 1 // 结束条件return fibonacciIterative(n-2) fibonacciIterative(n-1) // 递归公式 fn(n) fn(n-1)fn(n-2)
}这段代码是一个使用递归方式求解斐波那契数列的函数。该函数接收一个整数参数 n表示要求解的斐波那契数列的第 n 项n 从 1 开始计数。首先判断 n 是否小于 1如果是则返回 0如果 n 小于等于 2返回 1这两个条件是递归的结束条件。如果 n 大于 2则通过递归公式 fn(n) fn(n-1)fn(n-2) 计算第 n 项的值即该项的前两项之和继续调用 fibonacciIterative 函数求解第 n-1 和 n-2 项的值。递归函数会不断地向下调用自身直到满足结束条件才返回结果值。由于递归函数会反复调用自身并且存在重复计算因此在计算较大的斐波那契数列时可能会出现性能问题。// 优化的代码
1.向求解斐波那契数列时候将求解过程图形化可以看出有些已经
求过的结点我们还会反复在求如果把这些一求过的数存起来直接用也会
提高效率function fibonacciMemoization(n){const memo [0,1]const fibonacci (n) {if(meno[0] ! null) return memo[n]return memo[n] fibonacci(n - 1, memo) fibonacci(n - 2, memo);}return fibonacci(n);
} 树 二叉树搜索树 快速查找二叉树查找法 1.首先左侧节点存储比父节点小的值右侧节点存储比父节点大的值也就当我们每次去查的时候
只要去比较查询节点和当前比较父节点大小来决定他是走左面查询还是右面查询这样就不用去遍历
整个树 插入 1.插入后的数据一定要符合左侧节点存储比父节点小的值右侧节点存储比父节点大的值因此插入的时候也是要先和根节点比较直到找到末尾来决定插入的值是作为叶节点左侧还是右侧插入重复数据解决
1.二叉查找树中每一个节点不仅会存储一个数据因此我们通过链表和支持动态扩容的数组等数据结构把值相同的数据存储在同一个节点上
2.每个节点仍然只存储一个数据。在查找插入位置过程中如果碰到一个节点的值与要插入数据的值相同就将这个要插入的数据放到这个节点的右子树也就是说把这个新插入的数据当作大于这个节点的值来处理 排序 选择排序 思路
1.找到数据中最小值并将放到第一位然后找到第二小的将其放到第二位
2.选择排序分成两个区间分别是“排序区间”和“未排序区间”选择排序每次会从“未排序区间”中找到最小元素将其放到末尾
3.对引用图说明一下引用第一个图中的第二个数据说明 ‘1 5 6 3 2 4’,现在的1是排序区间‘5 6 3 2 4’是为了排序区间说明图虽然是5和2直接交换但实际末尾的4也是比较过了的只是图上没参与本次运算 1.这里有个思维转换当我们求一个数组中最小值和最大值的时候我们用等价替换的方法只是 循环了一次
问题来了当我们要把数组中所有的都进行排序那单单的一次循环肯定不够的这时候就是双层for 循环
2.这里还要注意的是选择排序的概念我们其实会将整个数组分成两个区域排序区间和未排序区间其中排序区间
是在数组前半部分因此已经排序过的地方肯定是不需要在进行排序因此第二层的循环条件也变成了let j i; j length; j// 选择排序function selectionSort(array, compareFn defaultCompare) {const {length} arraylet indexMinfor (let i 0; i length-1; i) {// 等价替换indexMin ifor (let j i; j length; j) {if (compareFn(array[indexMin], array[j]) Compare.BIGGER_THAN) {indexMin j}}if (i ! indexMin) {swap(array, i, indexMin)}}return array}console.log(selectionSort(array)) 插入排序 1.插入排序每次排一个数组项以此方式构建最后的排序数组。假定第一项已经排序了接着它和第二项进行比较第二项是应该待在原位还是插入到第一项之前呢这样头两项就正确排序接着和第三项比较以此类推
2.通俗的理解插入排序和选择排序 在整体思路方面差不多首先插入排序也是将整个排序分成两个区间分别是排序区间和未排序区间,每次会从未排序区间中取值去以排序区间中比较比较后将这个值插入到以排序区间
3.插入排序和选择排序 做个比较理解插入是从未排序区间取值在以排序区间去比较选择是从未排序区间
依次找到最小值放到以排序区间
4.如图红色区域就是已排序区间黄色就是未排序区间依次从黄色区域取值去红色区域比较并且将值插入到合适的红色区域 1.这里默认将第一个元素作为已排序区间中的内容这样方便后续逻辑
2.通过过动态图来理解下面插入算法中的while逻辑首先是吧整个数组分成两个区域
已排序区域 一个是 为排序区域第一层for是从为排序区域取出一个已排序区域就是
从当前这个值往后都是以排序区域因此while 的判断循环j 是从取点位置开始的注意
动图插入的那个动作如果你比我小我就把你往后移动如果你比我大我就到大了位置
整个while 就结束了这个值就到了j的位置// 插入排序function insertionSort(array, compareFn defaultCompare) {const {length} array;let temp;for (let i 1; i length; i) {let j i;temp array[i];while (j 0 compareFn(array[j - 1], temp) Compare.BIGGER_THAN) {array[j] array[j - 1];j--;}array[j] temp;}return array;};insertionSort(array)console.log(array)
结构 -- 数组 · js数据结构与算法 · 看云
