Recursion and stack

Two ways of thinking

// 創造 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

• 執行巢狀函式

• 當巢狀函式執行完畢取回原本的韓式繼續執行

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

// 假設有一間公司底下有分部門，部門下面要分子部門，子部門下面又分子子部門...
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

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

Recursive structures

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

// 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 };

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

list.next.next = secondList;

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 };

list.next = list.next.next;