一、遞回

1.1 概念

1.2 出口

1.3 遞回經典問題：遞回求斐波那契數列

1.4 遞回經典問題：遞回求階乘

1.5 遞回求一個數字各個位數上的數字的和

1.6 遞回遍歷DOM樹

二深淺拷貝

2.1 淺拷貝

2.2 深拷貝

2.3 如何區分深拷貝與淺拷貝？

2.3.1 淺拷貝：僅復制了參考，彼此之間的操作會互相影響

2.3.2 深拷貝：在堆中重新分配記憶體，不同的地址，互不影響

三總結

一、遞回

1.1 概念

遞回簡單的來說就是程式自己呼叫自己，就像下面這幅圖一樣，一直回圈往復，就像我們經常聽到的小和尚的故事，從前有座山，山里有座廟，廟里有個老和尚和一個小和尚，有一天老和尚對小和尚講故事，故事內容是：從前有座山，山里有座廟，廟里有個老和尚和一個小和尚，有一天老和尚對小和尚講故事，故事內容是：從前有座山，山里有座廟，廟里......

JavaScript的遞回就是在函式中呼叫函式自己，

// 遞回:函式中呼叫函式自己
function f1() {
	console.log("從前有座山，山里有座廟，廟里有個老和尚和一個小和尚，有一天老和尚對小和尚講故事，故事內容是：");
	f1();
}

f1();

1.2 出口

如果程式一直這樣回圈往復的呼叫自己，一直都不結束，就是一個死回圈，這沒什么意義，所以我們需要為遞回定義一個結束條件，即遞回的出口，當條件不滿足時，遞回一直前進，不斷地呼叫自己；當邊界條件滿足時，遞回回傳，

// 遞回的結束條件為i大于5
var i = 0;

function f1() {
	i++;
	if (i > 5) {
		return;
	}
	console.log("從前有座山，山里有座廟，廟里有個老和尚和一個小和尚，有一天老和尚對小和尚講故事，故事內容是：");
	f1();
}

f1();

遞回的應用通常是把一個大型的比較復雜的問題，通過層層轉化為一個與原問題相似的小的問題來求解，就像下邊統計排隊人數的問題，

上邊的這個小姐姐問第一個排隊的人，有多少人排隊，第一個人回答：我(1個人)+后邊的人，小姐姐沒有得到具體的答案，但是她知道只要弄清楚第一個人后邊有多少人排隊+第一個人就是排隊的人數，所以她繼續問后邊的人，結果得到了相同的回答，于是她得到的答案變成了：1+1+后邊的人，于是她不得不一直這樣問下去，等到問到最后一個人的時候，最后一個人回答，就我一個人，到此刻小姐姐終于得到了想要的答案即：1+1+········+1，上邊就是一個經典的遞回的例子，這里的遞回結束條件為是否是最后一個人，只要不是最后一個人，就一直問下去，

1.3 遞回經典問題：遞回求斐波那契數列

斐波那契數列（Fibonacci sequence），又稱黃金分割數列、指的是這樣的數列：0、1、1、2、3、5、8、13、21、34、……，從第三項開始，這個數列每一項都等于前兩項之和，在數學上，斐波那契數列被以遞推的方法定義：F(0)=0,F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*），下面的動圖描述了如何用遞回的方式來求斐波那契數列的第8項，即F(7)，根據定義F(7)=F(6)+F(5),求F(7)只需要知道F(6)和F(5)即可，而F(6)=F(5)+F(4),F(5)=F(4)+F(3).......依次類推，因為F(0)=0,F(1)=1是已知的，所以到第一項和第二項的時候就可以結束了，即遞回的結束條件是n=0或n=1，

遞回求斐波那契數列JS代碼實作:

// 遞回:求斐波那契數列
function getFib(x) {
	if (x == 0) {
		return 0
	} else if (x == 1) {
		return 1
	}
	return getFib(x - 1) + getFib(x - 2);
}
console.log(getFib(7)); // >13

1.4 遞回經典問題：遞回求階乘

n的階乘，就是從1開始乘到n，即1*2*3*...*(n-1)*n，即n!=1*2*3*...*(n-1)*n=n*(n-1)!，而(n-1)!=1*2*3*...*(n-1)=(n-1)*(n-2)!，......依次類推當n=1時，1！=1*0！=1，即遞回的結束條件為1，由此，可以得出遞回求階乘函式factorial()的演算法如下：

遞回求階乘JS代碼實作：

// 遞回案例:求5的階乘
function factorial(x) {
	if (x == 1) {
		return 1
	}
	return x * factorial(x - 1);
}
console.log(factorial(5)); // >120

1.5 遞回求一個數字各個位數上的數字的和

// 遞回案例:求一個數字各個位數上的數字的和:  123--->1+2+3=6                   
function getEverySum(x) {
	if (x < 10) {
		return x;
	}
	// 獲取的是這個數字的個位數
	return x % 10 + getEverySum(parseInt(x / 10));
}
console.log(getEverySum(123)); // >6

1.6 遞回遍歷DOM樹

<!DOCTYPE html>
<html lang="en">
        <head>
                <meta charset="UTF-8">
                <title>遞回遍歷DOM樹:公眾號AlbertYang</title>
        </head>

        <body>
                <h1>遍歷 DOM 樹</h1>
                <div>
                        <ul>
                                <li>123</li>
                                <li>456</li>
                                <li>789</li>
                        </ul>
                        <div>
                                <div>
                                        <span>haha</span>
                                </div>
                        </div>
                </div>
                <div id="demo_node">
                        <ul>
                                <li>123</li>
                        </ul>
                        <p>hello</p>
                        <h2>world</h2>
                        <div>
                                <p>dsa</p>
                                <h3>
                                        <span>dsads</span>
                                </h3>
                        </div>
                </div>

        </body>
        <script>
                // 獲取頁面中的根節點---根標簽
                var root = document.documentElement; // html
                // 函式遍歷DOM樹
                function forDOM(root1) {
                        // 獲取根節點中所有的子節點
                        var children = root1.children;
                        // 呼叫遍歷所有子節點的函式
                        forChildren(children);
                }
                // 把這個子節點中的所有的子節點顯示出來
                function forChildren(children) {
                        // 遍歷所有的子節點
                        for (var i = 0; i < children.length; i++) {
                                // 每個子節點
                                var child = children[i];
                                // 顯示每個子節點的名字
                                f1(child);
                                //  判斷child下面有沒有子節點,如果還有子節點,那么就繼續的遍歷
                                child.children && forDOM(child);
                        }
                }
                //函式呼叫,傳入根節點
                forDOM(root);

                function f1(node) {
                        console.log("節點的名字:" + node.nodeName);
                }
        </script></html>

二深淺拷貝

在JS中的資料型別可分為兩種：基本型別和參考型別，基本型別有undefined,null,Boolean,String,Number,Symbol等，參考型別有Object,Array,Date,Function,RegExp等，基本型別值在記憶體中占據固定大小，保存在堆疊記憶體中，參考型別的值是物件，保存在堆記憶體中，而堆疊記憶體儲的是物件的變數識別符號和物件在堆記憶體中的存盤地址，不同型別的復制方式是不同的，對于基本型別，從一個變數向另外一個新變數復制基本型別的值，會創建這個值的一個副本，并將該副本復制給新變數，對于參考型別，從一個變數向另一個新變數復制參考型別的值，其實復制的是指標，最終兩個變數都指向同一個物件，

2.1 淺拷貝

淺拷貝就是直接復制，相當于把一個物件中的所有的內容，復制一份給另一個物件，對于基本型別復制的是具體的值的副本，對于參考型別復制的是指標，

var obj1 = {
	age: 18,
	sex: "男",
	car: ["奔馳", "寶馬", "特斯拉"]
};
// 另一個物件
var obj2 = {};

// 把一個物件的屬性復制到另一個物件中,淺拷貝
// 把a物件中的所有的屬性復制到物件b中
function extend(a, b) {
	for (var key in a) {
		b[key] = a[key];
	}
}
extend(obj1, obj2);
console.dir(obj2); // 開始的時候這個物件是空物件，復制之后有了obj1的屬性
console.dir(obj1);

2.2 深拷貝

深拷貝還是復制，對于基本型別復制的是具體的值的副本，對于參考型別會找到物件中具體的屬性或者方法，并且開辟新的相應的空間，一個一個的復制到另一個物件中，在這個程序中需要使用遞回，

var obj1 = {
	age: 18,
	sex: "男",
	car: ["奔馳", "寶馬", "特斯拉"],
	dog: {
		name: "歡歡",
		age: 3,
		color: "黑白相間"
	}
};

var obj2 = {}; //空物件
// 利用遞回，把物件a中的所有的資料深拷貝到物件b中
function extend(a, b) {
	for (var key in a) {
		// 先獲取a物件中每個屬性的值
		var item = a[key];
		// 判斷這個屬性的值是不是陣列
		if (item instanceof Array) {
			// 如果是陣列,那么在b物件中添加一個新的屬性,并且這個屬性值也是陣列
			b[key] = [];
			// 呼叫這個方法，把a物件中這個陣列的屬性值一個一個的復制到b物件的這個陣列屬性中
			extend(item, b[key]);
		} else if (item instanceof Object) { // 判斷這個值是不是物件型別的
			// 如果是物件型別的,那么在b物件中添加一個屬性,是一個空物件
			b[key] = {};
			// 再次呼叫這個方法,把a物件中的屬性物件的值一個一個的復制到b物件的這個屬性物件中
			extend(item, b[key]);
		} else {
			// 如果值是普通的資料直接復制到b物件的這個屬性中
			b[key] = item;
		}
	}
}

extend(obj1, obj2);
console.dir(obj1);
console.dir(obj2);

2.3 如何區分深拷貝與淺拷貝？

假設B復制了A，當修改A時，看B是否會發生改變，如果B發生了改變，說明是淺拷貝，如果B沒有變，說明是深拷貝，淺拷貝中B復制的是A的參考，深拷貝中，B復制的是A的本體，上邊淺拷貝和深拷貝的代碼中，對于基本型別的值都是深拷貝，而對于參考型別值，淺拷貝復制的是參考，深拷貝復制的是具體的本體物件，

2.3.1 淺拷貝：僅復制了參考，彼此之間的操作會互相影響

var obj1 = {
	age: 18,
	sex: "男",
	car: ["奔馳", "寶馬", "特斯拉"]
};
// 另一個物件
var obj2 = {};

// 把一個物件的屬性復制到另一個物件中,淺拷貝
// 把a物件中的所有的屬性復制到物件b中
function extend(a, b) {
	for (var key in a) {
		b[key] = a[key];
	}
}
extend(obj1, obj2);
obj1.car[0] = "五菱宏光"; // 改變obj1中的值obj2也會改變
console.log(obj1);
console.log(obj2);

2.3.2 深拷貝：在堆中重新分配記憶體，不同的地址，互不影響

var obj1 = {
	age: 18,
	sex: "男",
	car: ["奔馳", "寶馬", "特斯拉"],
	dog: {
		name: "歡歡",
		age: 3,
		color: "黑白相間"
	}
};

var obj2 = {}; //空物件
// 通過函式實作，把物件a中的所有的資料深拷貝到物件b中
function extend(a, b) {
	for (var key in a) {
		// 先獲取a物件中每個屬性的值
		var item = a[key];
		// 判斷這個屬性的值是不是陣列
		if (item instanceof Array) {
			// 如果是陣列,那么在b物件中添加一個新的屬性,并且這個屬性值也是陣列
			b[key] = [];
			// 呼叫這個方法，把a物件中這個陣列的屬性值一個一個的復制到b物件的這個陣列屬性中
			extend(item, b[key]);
		} else if (item instanceof Object) { // 判斷這個值是不是物件型別的
			// 如果是物件型別的,那么在b物件中添加一個屬性,是一個空物件
			b[key] = {};
			// 再次呼叫這個方法,把a物件中的屬性物件的值一個一個的復制到b物件的這個屬性物件中
			extend(item, b[key]);
		} else {
			// 如果值是普通的資料直接復制到b物件的這個屬性中
			b[key] = item;
		}
	}
}

extend(obj1, obj2);
obj1.car[0] = "五菱宏光"; // 改變obj1中的值obj2不會改變
console.dir(obj1);
console.dir(obj2);