PDS/homework_1/matlab/recursiveKNN.m

function [neighbors, distances] = recursiveKNN(C, Q, k, m)
    % Recursive break, call knnsearch
    if size(C, 1) <= 1000 || size(Q, 1) <= 500  % Adjastable limit
        [neighbors, distances] = knnsearch(C, Q, 'K', k);
        return;
    end

    % Divide into subsets
    midC = floor(size(C, 1) / 2);
    midQ = floor(size(Q, 1) / 2);
    C1 = C(1:midC, :);
    C2 = C(midC+1:end, :);
    Q1 = Q(1:midQ, :);
    Q2 = Q(midQ+1:end, :);

    % Recursive calls
    [N1_1, D1_1] = recursiveKNN(C1, Q1, k, m);
    [N1_2, D1_2] = recursiveKNN(C2, Q1, k, m);
    [N2_1, D2_1] = recursiveKNN(C1, Q2, k, m);
    [N2_2, D2_2] = recursiveKNN(C2, Q2, k, m);

    % Merge
    [N1, D1] = mergeResultsWithM(N1_1, D1_1, N1_2, D1_2, C1, C2, k, m);
    [N2, D2] = mergeResultsWithM(N2_1, D2_1, N2_2, D2_2, C1, C2, k, m);

    % Combine results for Q1 and Q2
    neighbors = [N1; N2];
    distances = [D1; D2];

end