> For the complete documentation index, see [llms.txt](https://mistborn.gitbook.io/til-coding/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mistborn.gitbook.io/til-coding/javascript/recursion-and-stack.md).

# Recursion and stack

## Two ways of thinking

```javascript
// 創造 pow(x, n) 帶入參數得到 x 的 n 次方 
pow(x, n) = x**n
pow(2, 3) = 8
pow(2, 4) = 16

// 有 2 種思維模式
// 第 1 種用迴圈
function pow(x, n) {
  let result = 1;
  // multiply result by x n times in the loop
  for (let i = 0; i < n; i++) {
    result *= x;
  }
  return result;
}
alert( pow(2, 3) ); // 8

// 第 2 種用遞回
function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}
alert( pow(2, 3) ); // 8

              if n==1  = x // 遞回基礎
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)

// 遞回函式通常比較簡短       
function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}

// 巢狀函式使用次數有限制，10,000次是可以的，次數依據引擎不同而有差異，這限制遞回的使用，但遞回仍被
// 廣泛應用，因為讓程式碼更簡單更容易維護
```

## The execution context and stack

當函式執行巢狀函式時，會發生以下步驟

* 目前函式停止執行
* 執行內容被儲存到課書資料結構  *execution context stack*
* 執行巢狀函式
* 當巢狀函式執行完畢取回原本的韓式繼續執行

```javascript
function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1); // 停止執行函式，執行巢狀函式
  }
}
alert( pow(2, 3) );

Context: { x: 2, n: 1, at line 1 } pow(2, 1) // 返回 2
Context: { x: 2, n: 2, at line 5 } pow(2, 2) // 跳到 pow(2, 1)
Context: { x: 2, n: 3, at line 5 } pow(2, 3) // 跳到 pow(2, 2)

// 遞回消耗記憶體容量，求 N 次方需要 N 個執行內容，回圈相對來說更省記憶體，任何遞回都可以用迴圈改寫
// 迴圈一般來說更有效，但有時寫成迴圈比較複雜，優化顯得不值得，因此遞迴還是被使用，且簡短好維護。
```

## Recursive traversals

```javascript
// 假設有一間公司底下有分部門，部門下面要分子部門，子部門下面又分子子部門...
let company = { // the same object, compressed for brevity
  sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 600 }],
  development: {
    sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],
    internals: [{name: 'Jack', salary: 1300}]
  }
};

// 用遞回可以得到所有巢狀物件的值，用迴圈要寫好幾個巢狀迴圈
// The function to do the job
function sumSalaries(department) {
  if (Array.isArray(department)) { // case (1)
    return department.reduce((prev, current) => prev + current.salary, 0); // sum the array
  } else { // case (2)
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // recursively call for subdepartments, sum the results
    }
    return sum;
  }
}
alert(sumSalaries(company)); // 6700

// 這就是遞迴的威力，可以拿到任何巢狀物件的值且很好理解程式碼。
```

![](https://2384301684-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LS3vj0v55HiJ9Pkdigx%2F-LhcuBAXBhq0krL8xWdy%2F-Lhd2gTxiXGdIpJmLChm%2Frecursive-salaries%402x.png?alt=media\&token=7350e246-60fe-473e-a3d5-ab21731408f0)

## Recursive structures

除上述的公司組織是遞回，在網頁端 HTML、XML 也是遞回結構，HTML 標籤裡面包含內容、註解、其他HTML 標籤，以下在舉一個遞回例子，某些情況他會優於 array。

```javascript
// array 要新增或刪除開頭中間元素有些麻煩，會需要大量的執行程序，這時 linked-list 結構較好用，
// 但無法透過資料的順序快速找到要的值，我們也沒有很常需要這樣的操作，因此 array 還是被廣泛應用。
let arr = [obj1, obj2, obj3];

// linked-list
let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

// same
let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };
```

![](https://2384301684-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LS3vj0v55HiJ9Pkdigx%2F-Lhd2k0gq82kSog7Dq5N%2F-Lhd68j7wuzoS4veHZqZ%2Flinked-list%402x.png?alt=media\&token=dcb1aa4c-9b42-4236-93c6-8ce14fbca78b)

```javascript
let secondList = list.next.next;
list.next.next = null;

list.next.next = secondList;
```

![](https://2384301684-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LS3vj0v55HiJ9Pkdigx%2F-Lhd2k0gq82kSog7Dq5N%2F-Lhd6Ci3pmFycY3P6coy%2Flinked-list-split%402x.png?alt=media\&token=a45b71bb-dc11-4d69-88fd-f6fccd3bbb41)

```javascript
let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };

// prepend the new value to the list
list = { value: "new item", next: list };
```

![](https://2384301684-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LS3vj0v55HiJ9Pkdigx%2F-Lhd2k0gq82kSog7Dq5N%2F-Lhd6EyiJWvcg81Onn0d%2Flinked-list-0%402x.png?alt=media\&token=9a1c0fb7-9197-44b9-bf31-8d9dd62187fe)

```javascript
list.next = list.next.next;
```

![](https://2384301684-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LS3vj0v55HiJ9Pkdigx%2F-Lhd2k0gq82kSog7Dq5N%2F-Lhd6ICGi71c0pN17_s3%2Flinked-list-remove-1%402x.png?alt=media\&token=a215e0b1-25e7-4b19-bf11-2988adcb0dd6)