我正在try 编写一个尾部递归函数CONTAINS(TREE，ELEMENT)，如果元素存在于二叉树中，则返回TRUE，否则返回FALSE.
我写了递归函数，问题是我不知道如何使它尾部递归
let leaf = { val: 6 }
let tree = {
val: 10,
sx: {
val: 5,
sx: {
val: 13
},
dx: leaf
},
dx: {
val: 32,
sx: null,
dx: null
}
}
function contains(t,x) {
if(t.val == x)
return 1;
let res = 0 ;
if(t.sx)
res += contains(t.sx,x)
if(t.dx)
res += contains(t.dx,x)
return Boolean(res)
}
console.log(contains(tree,6))
我认为这不可能实现完全的尾递归，因为递归调用的数量可能是1或2(或0)-在2的情况下，您不能无条件地返回函数的最终计算，因为您不知道特定的递归调用will是否是函数的最终计算.
也就是说，您可以对代码进行一些改进.如果val个匹配，则返回true，如果它们为真，则立即返回第一个递归调用，而不是与res变量相加.第二个调用可以是尾递归的，因为在这一点上，分支中没有什么需要判断的.
let leaf = {
val: 6
}
let tree = {
val: 10,
sx: {
val: 5,
sx: {
val: 13
},
dx: leaf
},
dx: {
val: 32,
sx: null,
dx: null
}
}
function contains(t, x) {
if (t.val == x) {
return true;
}
// Recursive, but not tail recursive:
if (t.sx && contains(t.sx, x)) {
return true;
}
// Tail recursive:
return !t.dx ? false : contains(t.dx, x);
}
console.log(contains(tree, 6))