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に変更することで、すべての関数呼び出しをカウントするように変更できます。

これ（および一般的な再帰）の優れた点は、計算したいものの定義を実際に言い換えているだけだということです。私たちが支店から戻ってきた場合、私たちから下への支店の総数の定義は何ですか？私たちのために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 に答える