递归

递归（英语：Recursion）

程序调用自身的编程技巧称为递归（ 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 n==1 = x / pow(x, n) = \ else = x * pow(x, n - 1)

也就是说pow 递归地调用自身 直到 n == 1

javascript 递归运用（全面理解JavaScript递归尾递归）(1)

为了计算 pow(2, 4)，递归变体经过了下面几个步骤：

  1. pow(2, 4) = 2 * pow(2, 3)
  2. pow(2, 3) = 2 * pow(2, 2)
  3. pow(2, 2) = 2 * pow(2, 1)
  4. pow(2, 1) = 2

因此，递归将函数调用简化为一个更简单的函数调用，然后再将其简化为一个更简单的函数，以此类推，直到结果

尾递归

尾递归，即在函数尾位置调用自身（或是一个尾调用本身的其他函数等等）。尾递归也是递归的一种特殊情形。尾递归是一种特殊的尾调用，即在尾部直接调用自身的递归函数

尾递归在普通尾调用的基础上，多出了2个特征：

在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，递归次数过多容易造成栈溢出

这时候，我们就可以使用尾递归，即一个函数中所有递归形式的调用都出现在函数的末尾，对于尾递归来说，由于只存在一个调用记录，所以永远不会发生"栈溢出"错误

实现一下阶乘，如果用普通的递归，如下：

function factorial(n) { if (n === 1) return 1; return n * factorial(n - 1); } factorial(5) // 120

如果n等于5，这个方法要执行5次，才返回最终的计算表达式，这样每次都要保存这个方法，就容易造成栈溢出，复杂度为O(n)

如果我们使用尾递归，则如下：

function factorial(n, total) { if (n === 1) return total; return factorial(n - 1, n * total); } factorial(5, 1) // 120

可以看到，每一次返回的就是一个新的函数，不带上一个函数的参数，也就不需要储存上一个函数了。尾递归只需要保存一个调用栈，复杂度 O(1)

应用场景

数组求和

function sumArray(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; };

//案例1：求和,1-100 function sun(n){ if(n==1) return 1 } //案例2：递归方法1,1,2,3,5,8,13,21,34,55,89…求第 n 项 function fib(n) { if (n === 1 || n === 2) return 1 return fib(n - 2) fib(n - 1) } console.log(fib(3)) //案例3：深拷贝 function clone(o) { var temp = {} for (var key in o) { if (typeof o[key] == 'object') { temp[key] = clone(o[key]) } else { temp[key] = o[key] } } return temp } //案例4：递归组件 //组件在它的模板内可以递归的调用自己，只要给组件设置 name 组件就可以了。 //不过需要注意的是，必须给一个条件来限制数量，否则会抛出错误: max stack size exceeded //组件递归用来开发一些具体有未知层级关系的独立组件。比如：联级选择器和树形控件 function clone(o) { var temp = {} for (var key in o) { if (typeof o[key] == 'object') { temp[key] = clone(o[key]) } else { temp[key] = o[key] } } return temp } //hash模式和history模式 //这里的hash指的就是url后的 # 号以及后面的支付，比如说：www.baidu.com/#hashhash，其中#hashhash 就是我们期望的 hash值， //由于hash值的变化不会导致浏览器向服务器发送请求，而且在hash的改变会触发hashchange事件，浏览器的前进后退也能对其进行控制，所以在H5的history模式出现之前，基本都是使用hash模式来实现前端路由，代码如下 window.addEventListener('hashchange',function(event){ let newUrl=event.newURL;//hash改变后的新的URL let loadUrl=event.oldURL;//hash改变前的URL }) //history模式，以下是history的相关API： history.go(-1); // 后退一页 history.go(2); // 前进两页 history.forward(); // 前进一页 history.back(); // 后退一页 //规范新增 history.pushState(); // 添加新的状态到历史状态栈 history.replaceState(); // 用新的状态代替当前状态 history.state // 返回当前状态对象

内存泄漏是什么

内存泄漏（Memory leak）是在计算机科学中，由于疏忽或错误造成程序未能释放已经不再使用的内存

并非指内存在物理上的消失，而是应用程序分配某段内存后，由于设计错误，导致在释放该段内存之前就失去了对该段内存的控制，从而造成了内存的浪费

程序的运行需要内存。只要程序提出要求，操作系统或者运行时就必须供给内存

对于持续运行的服务进程，必须及时释放不再用到的内存。否则，内存占用越来越高，轻则影响系统性能，重则导致进程崩溃

javascript 递归运用（全面理解JavaScript递归尾递归）(2)

在C语言中，因为是手动管理内存，内存泄露是经常出现的事情。

char * buffer; buffer = (char*) malloc(42); // Do something with buffer free(buffer);

上面是 C 语言代码，malloc方法用来申请内存，使用完毕之后，必须自己用free方法释放内存。

这很麻烦，所以大多数语言提供自动内存管理，减轻程序员的负担，这被称为"垃圾回收机制"

内存生命周期：

内存也是有生命周期的，一般可以按顺序分为三个周期：

内存分配 -> 内存使用 -> 内存释放。

内存管理机制：

JavaScript是在创建变量（对象，字符串等）时自动进行了分配内存，并且在不使用它们时“自动”释放。 释放的过程称为垃圾回收。

JavaScript 内存管理机制和内存的生命周期是一一对应的。首先需要分配内存，然后使用内存，最后释放内存。

其中 JavaScript 语言不需要程序员手动分配内存，绝大部分情况下也不需要手动释放内存，对 JavaScript 程序员来说通常就是使用内存（即使用变量、函数、对象等）。

垃圾回收机制

Javascript 具有自动垃圾回收机制（GC：Garbage Collecation），也就是说，执行环境会负责管理代码执行过程中使用的内存

原理：垃圾收集器会定期（周期性）找出那些不在继续使用的变量，然后释放其内存

通常情况下有两种实现方式：

标记清除

JavaScript最常用的垃圾收回机制

当变量进入执行环境是，就标记这个变量为“进入环境“。进入环境的变量所占用的内存就不能释放，当变量离开环境时，则将其标记为“离开环境“

垃圾回收程序运行的时候，会标记内存中存储的所有变量。然后，它会将所有在上下文中的变量，以及被在上下文中的变量引用的变量的标记去掉

在此之后再被加上标记的变量就是待删除的了，原因是任何在上下文中的变量都访问不到它们了

随后垃圾回收程序做一次内存清理，销毁带标记的所有值并收回它们的内存

举个例子：

var m = 0,n = 19 // 把 m,n,add() 标记为进入环境。 add(m, n) // 把 a, b, c标记为进入环境。 console.log(n) // a,b,c标记为离开环境，等待垃圾回收。 function add(a, b) { a var c = a b return c }

引用计数

语言引擎有一张"引用表"，保存了内存里面所有的资源（通常是各种值）的引用次数。如果一个值的引用次数是0，就表示这个值不再用到了，因此可以将这块内存释放

如果一个值不再需要了，引用数却不为0，垃圾回收机制无法释放这块内存，从而导致内存泄漏

const arr = [1, 2, 3, 4]; console.log('hello world');

上面代码中，数组[1, 2, 3, 4]是一个值，会占用内存。变量arr是仅有的对这个值的引用，因此引用次数为1。尽管后面的代码没有用到arr，它还是会持续占用内存

如果需要这块内存被垃圾回收机制释放，只需要设置如下：

arr = null

通过设置arr为null，就解除了对数组[1,2,3,4]的引用，引用次数变为 0，就被垃圾回收了

小结

有了垃圾回收机制，不代表不用关注内存泄露。那些很占空间的值，一旦不再用到，需要检查是否还存在对它们的引用。如果是的话，就必须手动解除引用

常见内存泄露情况

意外的全局变量

一个未声明变量的引用会在全局对象中创建一个新的变量。在浏览器的环境下，全局对象就是window，也就是说：

function foo(arg) { bar = "this is a hidden global variable"; }

另一种意外的全局变量可能由 this 创建：

function foo() { this.variable = "potential accidental global"; } // foo 调用自己，this 指向了全局对象（window） foo();

上述使用严格模式，可以避免意外的全局变量

闭包引起的内存泄漏

闭包可以使变量常驻内存，但如果使用不当就会在成内存泄漏

var theThing = null; var replaceThing = function () { var originalThing = theThing; var unused = function () { if (originalThing) console.log("hi"); }; theThing = { longStr: new Array(1000000).join('*'), someMethod: function () { console.log(someMessage); } }; }; setInterval(replaceThing, 1000);

上面代码中，每次调用 replaceThing 时，theThing 都会得到新的包含一个大数组和新的闭包（someMethod）的对象。

同时，没有用到的那个变量持有一个引用了 originalThing（replaceThing 调用之前的 theThing）闭包。

关键的问题是每当在同一个父作用域下创建闭包作用域的时候，这个作用域是被共享的。在这种情况下，someMethod 的闭包作用域和 unused 的作用域是共享的。

unused 持有一个 originalThing 的引用。尽管 unused 从来没有被使用过，someMethod 可以在 theThing 之外被访问。

而且 someMethod 和 unused 共享了闭包作用域，即便 unused 从来都没有被使用过，它对 originalThing 的引用还是强制它保持活跃状态（阻止它被回收）。

当这段代码重复运行时，将可以观察到内存消耗稳定地上涨，并且不会因为 GC 的存在而下降。

本质上来讲，创建了一个闭包链表（根节点是 theThing 形式的变量），而且每个闭包作用域都持有一个对大数组的间接引用，这导致了一个巨大的内存泄露。

定时器也常会造成内存泄露

var someResource = getData(); setInterval(function() { var node = document.getElementById('Node'); if(node) { // 处理 node 和 someResource node.innerHTML = JSON.stringify(someResource)); } }, 1000);

如果id为Node的元素从DOM中移除，该定时器仍会存在，同时，因为回调函数中包含对someResource的引用，定时器外面的someResource也不会被释放

包括我们之前所说的闭包，维持函数内局部变量，使其得不到释放

function bindEvent() { var obj = document.createElement('XXX'); var unused = function () { console.log(obj, '闭包内引用obj obj不会被释放'); }; obj = null; // 解决方法 }

没有清理对DOM元素的引用同样造成内存泄露

const refA = document.getElementById('refA'); document.body.removeChild(refA); // dom删除了 console.log(refA, 'refA'); // 但是还存在引用能console出整个div 没有被回收 refA = null; console.log(refA, 'refA'); // 解除引用

包括使用事件监听addEventListener监听的时候，在不监听的情况下使用removeEventListener取消对事件监听

怎样避免内存泄漏

1）减少不必要的全局变量，或者生命周期较长的对象，及时对无用的数据进行垃圾回收；

2）注意程序逻辑，避免“死循环”之类的 ；

3）避免创建过多的对象 原则：不用了的东西要及时归还。

给大家分享我收集整理的各种学习资料，前端小白交学习流程，入门教程等回答-下面是学习资料参考。

前端学习交流、自学、学习资料等推荐 - 知乎

,