0

不确定是否发布到 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));
4

2 回答 2

3 
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 来更改它以计算所有函数调用。

关于这个（以及一般的递归）的很酷的事情是它实际上只是重新定义了你想要计算的内容。如果我们从一个分支返回，从我们向下的分支总数的定义是什么？一个给我们，添加到左侧和右侧。如果我在底部并且我正在返回，那么我们有多少分支？零。

于 2013-02-10T06:54:33.137 回答
1

最简单的方法是将计数器作为参数传递给递归函数本身，类似于以下内容：

func foo(bar, acc) {
    print bar;
    print acc;
    foo(bar+1, acc+1);
}

然后，当您最初调用该函数时，您可以执行以下操作：

foo(bar, 0);

显然还有比这更多的东西（您可能希望该函数做的不仅仅是打印当前变量，而且您可能还需要确保它有一个结束案例），但希望基本的想法出现了。我建议阅读有关模式匹配、折叠和尾递归的内容，我认为这对理解计数器和累积有很大帮助。为了有趣地解释它如何有用，我最近花了很多时间在Erlang上，它非常大量地利用递归和尾调用（可能没有直接在函数中使用的计数器，但通过使用有效地做同样的事情所述尾调用到列表为空的点。

于 2013-02-10T01:15:45.697 回答