是否在条件语句中进行递归调用？

Question

我正在尝试遍历以下递归代码来查找二叉树的深度，但不知道是否调用了条件语句中的递归调用：

var maxDepth = function (root) {
  return maxDepthHandler(root, 1);
};

var maxDepthHandler = function (root, depth) {
  if (!root) {
    return 0;
  }
  if (!root.right && !root.left) {
    return depth;
  }
  if (root.right && root.left) {
    // are these recursive functions called when checking the condition?
    if (
      maxDepthHandler(root.right, depth + 1) >
      maxDepthHandler(root.left, depth + 1)
    ) {
      return maxDepthHandler(root.right, depth + 1);
    } else {
      // for my follow up question: is this the first recursive call?
      return maxDepthHandler(root.left, depth + 1);
    }
  } else if (root.right !== null) {
    return maxDepthHandler(root.right, depth + 1);
  } else {
    return maxDepthHandler(root.left, depth + 1);
  }
};

给定下图：

        13
       /  \
      8    37
     / \   / \
    6  11 24 42

如果在条件语句中不调用递归调用，是否意味着运行ning maxDepth(13) 将导致 maxDepthHandler(root.left, depth + 1); 成为第一个递归调用？我认为这是因为在第一次调用时，如果不调用条件中的递归调用，则无法计算条件，因此 else 语句为运行.

Answer 1

是的，它们被调用，因为需要它们的值来确定是否进入if语句体。

Answer 2

在您的特定情况下，它们都会被调用。这意味着您可能应该捕获它们的值以避免重复努力：

let right = maxDepthHandler(root.right, depth + 1);
let left = maxDepthHandler(root.left, depth + 1);
if (right > left) {
  return right;
} else {
  return left;
}

或：

let right = maxDepthHandler(root.right, depth + 1);
let left = maxDepthHandler(root.left, depth + 1);
return right > left ? right : left;

或：

let right = maxDepthHandler(root.right, depth + 1);
let left = maxDepthHandler(root.left, depth + 1);
return Math.max(left, right);

或：

return Math.max(maxDepthHandler(root.left, depth + 1), maxDepthHandler(root.right, depth + 1));

作为旁注，因为您正在通过返回 0 来处理空 root 情况，我认为您在 root.right 和 root.left 上的大多数其他条件是如果您的整个函数变为：

，将自动处理 null

  if (!root) {
    return 0;
  }
  return Math.max(maxDepthHandler(root.left, depth + 1), maxDepthHandler(root.right, depth + 1));

但是，在某些情况下，条件语句中的函数调用不会被调用。例如：

if(foo(1) || foo(2)) {
...
}
if(foo(3) && foo(4)) {
...
}

在此示例中，如果 foo(1) returns true，则 || 运算符将短路而不会打扰呼叫 foo(2)。如果 foo(3) returns false，&& 运算符将短路，因此不会调用 foo(4)。

是否在条件语句中进行递归调用？

Are recursive calls made in a conditional statement?

algorithm

recursion

binary-tree

depth

conditional-statements