javascript - 这个合并排序的实现是否使用相互递归？

Question

这个 mergeSort 算法是否使用相互递归？我意识到 mergeSort 调用了 merge 函数并且它调用了自身 (mergeSort)，但是因为 merge 没有调用mergeSort 不是相互递归，只是递归吗？

function mergeSort(arr) {
    // split array
    ...
    return merge(mergSort(firstHalf), mergeSort(secondHalf));
}

function merge (array1, array2) {
    // merge both arrays
    ...
    return singleArray;
}

Answer 1

正确:这是简单的递归。相互递归也叫间接递归:A调用B； B 调用 A。

您的分析完全正确:如果merge 调用mergeSort，那么您将进行相互递归。在发布的代码中，对 merge 的调用是调用树上的一个简单的父子链接。