尾递归.md

javascript中尾递归例子，可在chrome console中运行

fibonacci

var table = [1,1];
function f(n) {
  if(n < table.length) {
    return table[n];
  }
  table[n] = f(n-1) + f(n-2);
  return table[n];
}
f(40);
function f_tail(n, acc1, acc2){
  if (n < 2)
    return acc1;
  return f_tail(n-1, acc2, acc1 + acc2);
}
f_tail(100,1,1);

不使用打表可以明显感觉到差别，但是使用打表之后无法比较区别...

计算链表长度

function Node() {
  this.value = 0;
  this.next = null;
}
Node.prototype.add = function(node) {
  this.next = node;
}
function getLength(head) {
  if (head === null) {
    return 0;
  }
  return getLength(head.next) + 1;
}

function getLengthTail(head, acc) {
  if (head === null) {
    return acc;
  }
  return getLengthTail(head.next, acc + 1);
}

var veryLongList = new Node();
var p = veryLongList;
for (var i = 0; i< 15580; i++){
  p.next = new Node();
  p = p.next;
}

getLengthTail(veryLongList, 0);
getLength(veryLongList);

验证结果似乎表明不支持尾递归优化

另一种验证尾递归的方式

var a = 0;
function count(n) {
  a = n;
  count(n+1);
}

chrome中确实栈溢出