合并排序的这种实现是否使用相互递归？(Does this implementation of merge sort use mutual recursion?)

合并排序的这种实现是否使用相互递归？(Does this implementation of merge sort use mutual recursion?)

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

Does this mergeSort algorithm use mutual recursion? I realize that mergeSort calls the merge function and it calls itself (mergeSort), but since merge does not call mergeSort is it not mutual recursion and simply just recursion?

function mergeSort(arr) { // split array ... return merge(mergSort(firstHalf), mergeSort(secondHalf)); } function merge (array1, array2) { // merge both arrays ... return singleArray; }

最满意答案

正确：这是简单的递归。 相互递归也称为间接递归：A调用B; B打电话给A.

你的分析是完全正确的： merge调用mergeSort ， 然后你会有相互递归。 在发布的代码中，对merge的调用是调用树上的简单父子链接。

Correct: this is simple recursion. Mutual recursion is also called indirect recursion: A calls B; B calls A.

Your analysis is exactly correct: were merge to call mergeSort, then you would have mutual recursion. In the posted code, the call to merge is a simple parent-child link on the call tree.