音乐网站的建设,自己开公司需要什么流程,市场调研报告ppt,代理公司名字一、递归 递归#xff08;英语#xff1a;Recursion#xff09; 在数学与计算机科学中#xff0c;是指在函数的定义中使用函数自身的方法 在函数内部#xff0c;可以调用其他函数。如果一个函数在内部调用自身本身#xff0c;这个函数就是递归函数 其核心思想是把一个大型… 一、递归 递归英语Recursion 在数学与计算机科学中是指在函数的定义中使用函数自身的方法 在函数内部可以调用其他函数。如果一个函数在内部调用自身本身这个函数就是递归函数 其核心思想是把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解 一般来说递归需要有边界条件、递归前进阶段和递归返回阶段。当边界条件不满足时递归前进当边界条件满足时递归返回 下面实现一个函数 pow(x, n)它可以计算 x 的 n 次方 使用迭代的方式如下
function pow(x, n) {let result 1;// 再循环中用 x 乘以 result n 次for (let i 0; i n; i) {result * x;}return result;
}使用递归的方式如下
function pow(x, n) {if (n 1) {return x;} else {return x * pow(x, n - 1);}
}pow(x, n) 被调用时执行分为两个分支 if n1 x/
pow(x, n) \else x * pow(x, n - 1)也就是说pow 递归地调用自身 直到 n 1 为了计算 pow(2, 4)递归变体经过了下面几个步骤
pow(2, 4) 2 * pow(2, 3)pow(2, 3) 2 * pow(2, 2)pow(2, 2) 2 * pow(2, 1)pow(2, 1) 2
因此递归将函数调用简化为一个更简单的函数调用然后再将其简化为一个更简单的函数以此类推直到结果
二、尾递归
尾递归即在函数尾位置调用自身或是一个尾调用本身的其他函数等等。尾递归也是递归的一种特殊情形。尾递归是一种特殊的尾调用即在尾部直接调用自身的递归函数
尾递归在普通尾调用的基础上多出了2个特征
在尾部调用的是函数自身可通过优化使得计算仅占用常量栈空间
在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储递归次数过多容易造成栈溢出
这时候我们就可以使用尾递归即一个函数中所有递归形式的调用都出现在函数的末尾对于尾递归来说由于只存在一个调用记录所以永远不会发生栈溢出错误
实现一下阶乘如果用普通的递归如下
function factorial(n){if(n1) return 1return n * factorial(n-1)
}
undefined
factorial(5)
120如果n等于5这个方法要执行5次才返回最终的计算表达式这样每次都要保存这个方法就容易造成栈溢出复杂度为O(n)
如果我们使用尾递归则如下
function factorial(n,total1){if(n1) return totalreturn factorial(n-1,n*total)
}
factorial(5) // 120可以看到每一次返回的就是一个新的函数不带上一个函数的参数也就不需要储存上一个函数了。尾递归只需要保存一个调用栈复杂度 O(1)
二、应用场景
数组求和
function sum(arr, total) {if(arr.length 1) {return total}return sum(arr, total arr.pop())
}使用尾递归优化求斐波那契数列
function factorial2 (n, start 1, total 1) {if(n 2){return total}return factorial2 (n -1, total, total start)
}数组扁平化
let a [1,2,3, [1,2,3, [1,2,3]]]
// 变成
let a [1,2,3,1,2,3,1,2,3]
// 具体实现
function flat(arr [], result []) {arr.forEach(v {if(Array.isArray(v)) {result result.concat(flat(v, []))}else {result.push(v)}})return result
}数组对象格式化
let obj {a: 1,b: {c: 2,D: {E: 3}}
}
// 转化为如下
let obj {a: 1,b: {c: 2,d: {e: 3}}
}// 代码实现
function keysLower(obj) {let reg new RegExp(([A-Z]), g);for (let key in obj) {if (obj.hasOwnProperty(key)) {let temp obj[key];if (reg.test(key.toString())) {// 将修改后的属性名重新赋值给temp并在对象obj内添加一个转换后的属性temp obj[key.replace(reg, function (result) {return result.toLowerCase()})] obj[key];// 将之前大写的键属性删除delete obj[key];}// 如果属性是对象或者数组重新执行函数if (typeof temp object || Object.prototype.toString.call(temp) [object Array]) {keysLower(temp);}}}return obj;
};
