algorithm - 我应该在递归函数中的什么地方放置计数器？

Question

不确定是发布到 PSE 还是 SO，但我的问题是关于递归。

假设我有一些递归运行的函数 MergeSort。如果我想计算它拆分数组前半部分的次数，我应该把计数器放在哪里？ (我知道我可以计算它，但我正在努力更好地理解递归)。

所以，例如

function u = MergeSort(Array)  

%% Initializations
A = Array;
B = zeros(1,n2);    %to store first half of A
C = zeros(1,n1-n2); %to store second half of A
D = zeros(1,n1);    %to store sorted array
na = length(A);
nb = floor(0.5*na);
count1 = 0;
count2 = 0;

%% recursive part
if n1 == 1
  D = A;
  A1 = mergeSort(A(1:nb));
  A2 = mergeSort(A(nb+1:n));

Answer 1

function (sorted_array, total) =  mergesort(array) {
  if(length(array) == 1) 
  then return (array, 0); // this is not a split, don't count it

  (left, left_sum) = mergesort(lefthalf);
  (right, right_sum) = mergesort(righthalf);

  result_array = merge(left, right);

  return (result_array, 1 + left_sum + right_sum); // this is a split, add 1
}

这不会只计算上半场的拆分次数，但您可以仅在上半场调用它。您可以通过将 0 更改为 1 来更改它以计算所有函数调用。

关于此(以及一般的递归)的最酷之处在于，它实际上只是重申了您要计算的内容的定义。如果我们从一个分支返回，那么从我们往下的分支总数的定义是什么？一个给我们，添加到左边和右边的许多。如果我在底部并且我要返回，那么我们向下有多少分支？零。